Module 4 · Array Greedy

Candy

HardProblem 12 of 21 10 min read ~25 min to solve LeetCode

GreedyArrayTwo PassesLocal Constraints

Asked atAmazonGoogleMicrosoftMetaApple

Problem Statement

There are n children standing in a line. Each child has a rating. You must give every child at least one candy, and any child with a higher rating than an immediate neighbor must receive more candies than that neighbor. Return the minimum number of candies needed.

Input

An integer array ratings, where ratings[i] is the rating of child i.

Output

An integer: the minimum total candies satisfying both neighbor rules.

Constraints

•1 <= ratings.length <= 2 * 10^4
•0 <= ratings[i] <= 2 * 10^4

Examples

Example 1

Input:

ratings = [1,0,2]

Output: 5

Explanation: Give candies [2,1,2]. Both children with rating 1 and 2 are higher than the middle child, so both need more candies.

Example 2

Input:

ratings = [1,2,2]

Output: 4

Explanation: Give candies [1,2,1]. The last two ratings are equal, so the last child does not need more than the middle child.

Learning Objectives

Break bidirectional neighbor constraints into two one-directional greedy passes.
Use minimum candies from the left rule and then reconcile the right rule with **max**.
Explain why every child can start with one candy without losing optimality.
Distinguish strict greater-than constraints from equal-rating neighbors.

Intuition

Greedy Insight: give every child one candy, then enforce the left-neighbor rule from left to right. If ratings[i] > ratings[i - 1], child i must have one more candy than child i - 1. Then enforce the right-neighbor rule from right to left. If ratings[i] > ratings[i + 1], child i must have at least one more candy than child i + 1, so take the max of its current value and that requirement.

The important detail is max. The left pass may already have assigned enough candies to satisfy an increasing run from the left. The right pass should only raise values that are too small; lowering would break constraints already satisfied.

Common mistakes

×Using one pass and missing a higher-rated child that must beat its right neighbor.
×Overwriting the left-to-right candies during the right pass instead of taking **max**.
×Treating equal ratings as if one side must receive more candies.
×Trying to sort children by rating, which destroys the original neighbor relationships.

Algorithm Explanation

Greedy strategy

Start with 1 candy for every child. The left-to-right pass gives each child the minimum amount needed to be greater than a lower-rated left neighbor. The right-to-left pass gives each child the minimum additional amount needed to be greater than a lower-rated right neighbor, using max to preserve the left rule.

Why it works

Each neighbor constraint is local and directional. The left pass independently satisfies all constraints of the form ratings[i] > ratings[i - 1] with the smallest possible candies for those constraints. The right pass independently satisfies all constraints of the form ratings[i] > ratings[i + 1] without reducing any already valid assignment.

Proof of correctness

After the left pass, every rising edge from left to right is satisfied with the minimum value forced by that rising chain. Consider the right pass at index i. If ratings[i] <= ratings[i + 1], no right-neighbor constraint forces more candies, so leaving the value unchanged is optimal. If ratings[i] > ratings[i + 1], any valid assignment must give child i at least candies[i + 1] + 1. Setting candies[i] to the maximum of its current value and that forced amount is the smallest value that satisfies both the already processed right constraint and the left-pass constraints. By induction from right to left, all right constraints are satisfied without unnecessary increases. Since every candy increase is forced by at least one neighbor constraint, the final sum is minimal.

Algorithm

Create a candies array of length n and fill it with 1.
Scan left to right from index 1. If the current rating is greater than the left rating, set current candies to left candies plus 1.
Scan right to left from index n - 2. If the current rating is greater than the right rating, set current candies to max(current, right candies + 1).
Sum the candies array and return the total.

Solutions

Solution: Two directional passes

Handle one direction at a time. The first pass satisfies all increasing relationships from the left. The second pass satisfies all increasing relationships from the right while preserving the first pass with max.

Step-by-step

Allocate candies and fill it with 1 because every child must receive at least one candy.
Walk left to right. When a child has a higher rating than the left neighbor, assign one more candy than that neighbor.
Walk right to left. When a child has a higher rating than the right neighbor, raise its candy count to at least one more than the right neighbor.
Sum all candy counts to produce the minimum total.

Time

O(n)

Space

O(n)

Two linear passes plus one summation; the candies array stores the final assignment.

Java implementation

Loading…

Dry Run

Sample input

ratings = [1,0,2]. Start every child with one candy, then reconcile the left and right neighbor rules.

phase	index	rating comparison	candies before	candies after
initial	all	minimum one candy each	[]	[1,1,1]
left to right	1	0 > 1 is false	[1,1,1]	[1,1,1]
left to right	2	2 > 0 is true	[1,1,1]	[1,1,2]
right to left	1	0 > 2 is false	[1,1,2]	[1,1,2]
right to left	0	1 > 0 is true	[1,1,2]	[2,1,2]

The final candies array is [2,1,2], whose sum is 5. Both neighbor constraints are satisfied with no extra candies.

Interview Tips

Lead with the decomposition: one pass cannot see both directions cleanly, so satisfy the left constraint first and the right constraint second. Emphasise strict comparison; equal ratings impose no ordering. If the interviewer asks about O(1) space, discuss slope counting only after the two-pass solution is correct.

Likely follow-ups

Can you solve Candy in O(1) extra space using increasing and decreasing slope lengths?
How would you return the actual candies array instead of only the total?
What changes if equal ratings must receive equal candies?
How would the problem change if children stood in a circle?

Key Takeaways

Bidirectional local constraints can often be split into two directional passes.
Initialising everyone to the minimum valid value keeps the solution minimal.
The second pass must use **max** so it fixes new constraints without breaking old ones.
Equal ratings do not force a candy ordering because the rule is strictly higher rating.

Reusable template: Two-pass constraint greedy: satisfy all left-facing local constraints, then satisfy all right-facing constraints by only increasing values that need to be higher.