Candy

Difficulty: Hard Source: NeetCode

Problem

There are n children standing in a line. Each child has a rating value. You are giving candies to these children with the following requirements:

• Each child must have at least one candy.
• Children with a higher rating than an adjacent child must get more candies than that neighbour. Return the minimum number of candies you need to have.

Example 1: Input: ratings = [1, 0, 2] Output: 5 Explanation: Candies: [2, 1, 2]

Example 2: Input: ratings = [1, 2, 2] Output: 4 Explanation: Candies: [1, 2, 1]

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Two-pass greedy — making one pass left-to-right, another right-to-left
• Array manipulation — maintaining a separate result array

1. Brute Force — Repeated Passes

Intuition

Start with everyone getting 1 candy. Repeatedly scan for violations (a child with a higher rating than a neighbour but not more candies). Fix each violation. Repeat until no violations remain. This is correct but slow — it may take many passes.

Algorithm

1. Initialise candies = [1] * n.
2. Repeat until stable:
   • For each i from 0 to n-1:
     • If ratings[i] > ratings[i-1] and candies[i] <= candies[i-1]: candies[i] = candies[i-1] + 1.
     • If ratings[i] > ratings[i+1] and candies[i] <= candies[i+1]: candies[i] = candies[i+1] + 1.
3. Return sum(candies).

Solution

def candy(ratings):
    n = len(ratings)
    candies = [1] * n
    changed = True

    while changed:
        changed = False
        for i in range(n):
            if i > 0 and ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1]:
                candies[i] = candies[i - 1] + 1
                changed = True
            if i < n - 1 and ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
                candies[i] = candies[i + 1] + 1
                changed = True

    return sum(candies)


print(candy([1, 0, 2]))   # 5
print(candy([1, 2, 2]))   # 4
print(candy([1, 3, 2, 2, 1]))  # 7

Complexity

• Time: O(n²) — up to n passes, each O(n)
• Space: O(n)

2. Greedy — Two Passes

Intuition

Do it in exactly two passes:

Left-to-right pass: If ratings[i] > ratings[i-1], then candies[i] = candies[i-1] + 1. This ensures children with higher ratings than their left neighbour get more candies.

Right-to-left pass: If ratings[i] > ratings[i+1], then candies[i] = max(candies[i], candies[i+1] + 1). This ensures children with higher ratings than their right neighbour also get more candies. We take the max to respect both constraints simultaneously.

The answer is the sum of the final candy array.

Algorithm

1. candies = [1] * n.
2. Left-to-right: for i in 1..n-1, if ratings[i] > ratings[i-1], candies[i] = candies[i-1] + 1.
3. Right-to-left: for i in n-2..0, if ratings[i] > ratings[i+1], candies[i] = max(candies[i], candies[i+1] + 1).
4. Return sum(candies).

Solution

def candy(ratings):
    n = len(ratings)
    candies = [1] * n

    # Left-to-right: enforce left neighbour constraint
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1

    # Right-to-left: enforce right neighbour 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)


print(candy([1, 0, 2]))            # 5  → [2, 1, 2]
print(candy([1, 2, 2]))            # 4  → [1, 2, 1]
print(candy([1, 3, 2, 2, 1]))     # 7  → [1, 3, 2, 2, 1] wait... let's check
# ratings: [1, 3, 2, 2, 1]
# L-R: [1, 2, 1, 1, 1]
# R-L: i=3: 2>1? no. i=2: 2>2? no. i=1: 3>2? yes -> max(2, 1+1)=2. i=0: 1>3? no.
# Result: [1, 2, 1, 1, 1] → sum = 6
print(candy([1, 3, 2, 2, 1]))     # 6  → [1, 2, 1, 1, 1]
print(candy([1, 2, 87, 87, 87, 2, 1]))  # 13
print(candy([3]))                  # 1
print(candy([1, 2, 3, 4, 5]))     # 15 → [1, 2, 3, 4, 5]
print(candy([5, 4, 3, 2, 1]))     # 15 → [5, 4, 3, 2, 1]

Complexity

• Time: O(n)
• Space: O(n)

Common Pitfalls

Using only one pass. A single left-to-right pass misses the case where a child needs more candy because of their right neighbour. You need both passes — left-to-right for left constraints, right-to-left for right constraints.

Assigning in the right-to-left pass without max. If you do candies[i] = candies[i+1] + 1 without max, you overwrite the left-to-right result and may violate the left neighbour constraint. Always take max(candies[i], candies[i+1] + 1).

Thinking equal ratings need equal candies. The problem only says children with higher ratings than a neighbour need more candy. Equal ratings have no constraint between them — each just needs at least 1. [1, 2, 2] correctly gives [1, 2, 1], not [1, 2, 2].