Candy Solution | SkillFlow

Problem

You have n children standing in a line, each assigned a rating score. Hand out candy so that every child gets at least one piece, and any child with a strictly higher rating than an adjacent neighbor must receive more candy than that neighbor. Find the minimum total number of candies needed.

Input: ratings = [1, 0, 2]
Output: 5
Explanation: Child 0 gets 2, child 1 gets 1, child 2 gets 2 — the only valid minimum distribution.

A tricky case: ratings = [1, 2, 2] → output 4. The third child has the same rating as the second, so they can both receive just 1 candy (the constraint only triggers on strictly greater).

Intuition

Each child's candy count is constrained by both neighbors, but the left-neighbor and right-neighbor constraints are independent — they never conflict with each other on the same child. That means we can satisfy each direction in its own pass, then combine. The greedy insight is that a single left-to-right scan handles all left-neighbor constraints perfectly, and a single right-to-left scan handles all right-neighbor constraints — as long as we take the maximum at each position when merging.

Approach 1 — Brute Force (Repeated Passes)

Initialize every child to 1 candy, then repeatedly scan the array and bump up any child whose candy count violates either neighbor constraint. Stop when a full scan produces no changes.

Set candies[i] = 1 for every child.
Scan left to right: if ratings[i] > ratings[i-1] but candies[i] <= candies[i-1], set candies[i] = candies[i-1] + 1 and mark that a change occurred.
In the same scan, check the right neighbor with the same logic.
Repeat until no changes occur in a full scan.
Return the sum of candies.

1def candy(ratings: list[int]) -> int:
2    n = len(ratings)
3    candies = [1] * n
4    changed = True
5    while changed:  # keep scanning until the array fully stabilizes
6        changed = False
7        for i in range(n):
8            if i > 0 and ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1]:
9                candies[i] = candies[i - 1] + 1
10                changed = True
11            if i < n - 1 and ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
12                candies[i] = candies[i + 1] + 1
13                changed = True
14    return sum(candies)

Time: O(n²) — a strictly decreasing input like [5,4,3,2,1] requires O(n) passes, each touching O(n) elements.

Space: O(n) — the candies array.

Approach 2 — Two-Pass Greedy

Do exactly two linear scans: one left-to-right that satisfies every left-neighbor constraint, then one right-to-left that satisfies every right-neighbor constraint. At each position in the second pass, take the maximum of the two passes' values so the left-pass result is never overwritten.

Initialize candies[i] = 1 for all children.
Left-to-right pass: if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1.
Right-to-left pass: if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1).
Return the sum.

1def candy(ratings: list[int]) -> int:
2    n = len(ratings)
3    candies = [1] * n
4
5    for i in range(1, n):
6        if ratings[i] > ratings[i - 1]:
7            candies[i] = candies[i - 1] + 1  # must beat left neighbor
8
9    for i in range(n - 2, -1, -1):
10        if ratings[i] > ratings[i + 1]:
11            # must beat right neighbor, but also keep left-pass result if larger
12            candies[i] = max(candies[i], candies[i + 1] + 1)
13
14    return sum(candies)

Time: O(n) — exactly two linear passes over the array.

Space: O(n) — the candies array.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(n)	Only for understanding — correct but too slow for large inputs
Two-Pass Greedy	O(n)	O(n)	Always — clean, fast, and handles all edge cases

Common Mistakes

Overwriting the left-pass result in the right-to-left pass — writing candies[i] = candies[i+1] + 1 instead of candies[i] = max(candies[i], candies[i+1] + 1) destroys the work done in the first pass, producing the wrong answer for sequences like [1,3,2,2,1].
Treating equal ratings as requiring equal candy — the constraint says strictly higher rating requires more candy; two children with the same rating can receive different amounts, and the minimum is to give them each 1.
Doing only the left-to-right pass — this satisfies every child's left-neighbor constraint but ignores the right neighbor, failing on any strictly decreasing suffix (e.g., [5,4,3,2,1] would incorrectly return 5 instead of 15).
Using >= instead of > in the comparison — this would force children with equal ratings to have different candy counts, increasing the total unnecessarily and potentially producing wrong answers.
Starting from 0 instead of 1 — every child must receive at least one candy regardless of rating, so the initial array must be all 1s, not all 0s.

Candy — Solution