135 - Candy

Difficulty: Hard | Pattern: Greedy (Two-Pass) | Company tags: Amazon, Google, Snapchat

Problem Statement

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.
• Children with a higher rating than their neighbors must get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: Give [2,1,2] candies → 5 total

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: Give [1,2,1] candies → 4 total

Algorithm Flow

Approach: Two-Pass Greedy — O(n), O(n)

Key insight: Satisfying the constraint for both neighbors simultaneously is hard. Instead:

1. Left-to-right pass: If child i has higher rating than child i-1, give candies[i] = candies[i-1] + 1.
2. Right-to-left pass: If child i has higher rating than child i+1, ensure candies[i] = max(candies[i], candies[i+1] + 1).

The max ensures we satisfy BOTH constraints.

def candy(ratings: list[int]) -> int:
    n = len(ratings)
    candies = [1] * n
    
    # Left to right: satisfy left neighbor constraint
    for i in range(1, n):
        if ratings[i] > ratings[i-1]:
            candies[i] = candies[i-1] + 1
    
    # Right to left: satisfy right neighbor constraint
    for i in range(n-2, -1, -1):
        if ratings[i] > ratings[i+1]:
            candies[i] = max(candies[i], candies[i+1] + 1)
    
    return sum(candies)

Dry Run

ratings = [1, 0, 2]

Step	Action	candies
Init	all ones	[1, 1, 1]
L→R i=1	ratings[1]=0 not gt ratings[0]=1	[1, 1, 1]
L→R i=2	ratings[2]=2 gt ratings[1]=0 → candies[2]=2	[1, 1, 2]
R→L i=1	ratings[1]=0 not gt ratings[2]=2	[1, 1, 2]
R→L i=0	ratings[0]=1 gt ratings[1]=0 → candies[0]=max(1,1+1)=2	[2, 1, 2]

Sum = 5 ✓

ratings = [1, 2, 2]

Step	Action	candies
Init	all ones	[1, 1, 1]
L→R i=1	2 gt 1 → candies[1]=2	[1, 2, 1]
L→R i=2	2 not gt 2 (equal)	[1, 2, 1]
R→L i=1	2 not gt 2	[1, 2, 1]
R→L i=0	1 not gt 2	[1, 2, 1]

Sum = 4 ✓ (equal ratings don't need different candy counts)

Edge Cases

• All same ratings → each gets 1 candy → return n
• Strictly increasing → [1,2,3,...,n] candies
• Strictly decreasing → [n,...,2,1] candies
• Single child → return 1
• Equal adjacent ratings → treated as no constraint between them

Complexity

• Time: O(n) — two linear passes
• Space: O(n) — candies array

Note: An O(1) space solution exists using a "valley-and-peak" counting approach but is significantly more complex to implement correctly. The two-pass O(n) space solution is preferred in interviews.

Key Terms

Term	Definition
Two-pass greedy	Solving a bidirectional constraint by making two independent, direction-limited passes and combining results with max
Local constraint	A rule that only compares a child to its immediate neighbor, not the whole array
Monotonic run	A maximal strictly increasing or decreasing sequence of ratings, which determines how high the candy count climbs
Valley-and-peak counting	An O(1) space alternative that tracks the length of increasing/decreasing runs without an auxiliary array

FAQ

Q: Why can't one pass solve this? A: A single left-to-right (or right-to-left) pass can only satisfy the constraint relative to one neighbor. A child with a higher rating than both neighbors needs information from both directions, so two passes are needed and combined with max.

Q: Why take max(candies[i], candies[i+1] + 1) in the second pass instead of overwriting? A: Overwriting could violate the constraint already established in the first pass (with the left neighbor). Taking the max guarantees both constraints hold simultaneously.

Q: What happens with equal adjacent ratings? A: Equal ratings impose no ordering constraint, so neither pass increments the candy count across that boundary — both children can have the same count.

Q: Can this be solved with O(1) extra space? A: Yes, using a single pass that tracks the lengths of the current increasing and decreasing runs (and the peak value), but it's harder to get right under interview time pressure; the two-array-pass approach is the standard answer.

Q: What's the minimum possible output? A: n, when all ratings are equal (every child gets exactly one candy).

Quick Revision

• Pattern: greedy, two independent linear passes.
• Each child starts with 1 candy.
• Left-to-right pass fixes the "higher than left neighbor" constraint.
• Right-to-left pass fixes the "higher than right neighbor" constraint using max(current, right+1).
• max in the second pass is essential — it merges both constraints without violating the first pass's work.
• Equal adjacent ratings never force a candy increase.
• Answer is sum(candies).
• Time O(n), space O(n); an O(1)-space variant exists but is more complex.

Related Problems

• 1354 - Construct Target Array With Multiple Sums — another greedy problem reasoning about array reconstruction under local rules
• 1696 - Jump Game VI — shares the theme of making optimal local decisions across an array in one or two passes
• Pattern match: "distribute values under neighbor-relative constraints" problems generally reduce to two directional passes combined with min/max