Interview Classic 150 Questions P135 Distribute Candies

---

Timeline

timeline

2025-10-20

init

greedy

---

Title:

P135 Distribute Candies

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 uphill elements, scanning from right to left handles downhill elements. For the boundary between uphill and downhill, we need to take the maximum of the left requirement and right requirement plus 1, so that it satisfies both uphill and downhill.

Initialize by giving each person one candy.

🍬 Step 1: Left to Right
Ensure that children with higher ratings than the left get more candies:

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

🍬 Step 2: Right to Left

Ensure that children with higher ratings than the right get 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 from left to right, because the right needs to reference the left.
• Downhill from 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);
	}
};