Interview Classic 150 Problem P135: Distribute Candy

---

Timeline

Timeline

2025-10-20

init

Greedy

---

Problem:

P135 Distribute Candy

https://leetcode.cn/problems/candy/description/?envType=study-plan-v2&envId=top-interview-150

Imagine ratings form a continuous mountain range. Initially we set all to 1, which is flat ground. Scanning from left to right handles all elements on the uphill slope, and scanning from right to left handles elements on the downhill slope. For the boundary point between uphill and downhill, it must be the maximum of the left requirement and the right requirement plus 1, so that it satisfies both the uphill and downhill.

Initialize by giving each person one candy.

🍬 Step 1: Left to Right
Ensure that a child with a higher rating than the left neighbor gets more candies:

if (ratings[i] > ratings[i-1])
    candy[i] = candy[i-1] + 1

🍬 Step 2: Right to Left

Ensure that a child with a higher rating than the right neighbor gets more candies, while taking the maximum with the existing value (to avoid breaking the left-to-right rule):

if (ratings[i] > ratings[i+1])
  candy[i] = max(candy[i], candy[i+1] + 1)

• Uphill goes left to right, because the right side needs to reference the left side.
• Downhill goes right to left, because the left side needs to reference the right side.

Code:

#include <numeric>
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    public:
	int candy(vector<int> &ratings)
	{
		int i, n = ratings.size();

		vector<int> candies(n, 1);
		// left to right
		for (i = 1; i < n; i++) {
			if (ratings[i] > ratings[i - 1]) {
				candies[i] = candies[i - 1] + 1;
			}
		}
		// right to left
		for (i = n - 2; i >= 0; i--) {
			if (ratings[i] > ratings[i + 1]) {
				candies[i] = std::max(candies[i + 1] + 1,
						      candies[i]);
			}
		}

		return std::accumulate(candies.begin(), candies.end(), 0);
	}
};