DSA problem
Candy
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: each child must have at least one candy, and children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children.
The constraint "higher rating gets more candy than neighbors" links every child to BOTH of their neighbors. A correct solution must satisfy these two directional constraints simultaneously, which is what makes the problem subtle. A natural attempt — process children left to right with a running count — handles only the left neighbor relationship and gets the right side wrong.
The standard greedy uses two passes. In the first pass (left to right), set candy[i] = candy[i-1] + 1 whenever ratings[i] > ratings[i-1]; otherwise reset to 1. This enforces the rising-from-the-left rule. In the second pass (right to left), set candy[i] = max(candy[i], candy[i+1] + 1) whenever ratings[i] > ratings[i+1]. This enforces the rising-from-the-right rule without violating the left side, because we only ever raise values.
Taking the maximum of the two passes ensures both inequalities hold and never wastes candy: any solution must satisfy each unilateral constraint, so the minimum of candy[i] is bounded below by both expressions, and the algorithm hits that lower bound exactly. The total work is O(n) time and O(n) extra space for the candy array. There is also a constant-space O(n) "slope" approach, but the two-pass version is the cleanest standard answer.
Examples
ratings = [1,0,2]5ratings = [1,2,2]4ratings = [1,3,4,5,2]11Constraints
- n == ratings.length
- 1 <= n <= 2 * 10^4
- 0 <= ratings[i] <= 2 * 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.