TL;DR
Two greedy sweeps (left→right, then right→left) and take the per-child max — O(n) time, O(n) space; an O(1)-space slope-counting variant follows.
Approach 1 — Brute force (relax until stable)
Give everyone 1 candy, then repeatedly scan the row: whenever a child outranks a neighbor but doesn’t have more candy, bump it up by one. Keep looping until a full pass changes nothing.
from typing import List
def candy(ratings: List[int]) -> int:
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)
Complexity: O(n^2) worst case (a long monotone run propagates one bump per pass), O(n) space. Correct, but it re-derives the same increments many times.
Approach 2 — Two-pass greedy (left sweep, right sweep, take max)
Greedy-choice property (why per-neighbor local mins compose optimally). Each child’s constraint splits cleanly into two independent one-directional constraints: “more than my left neighbor if I outrank it” and “more than my right neighbor if I outrank it.”
- The left→right sweep assigns each child the minimum candy that satisfies only the left-neighbor rule:
1 if it doesn’t outrank its left neighbor, else left value + 1. This is forced — you cannot give less and still obey the left rule — so it is a lower bound for that direction.
- The right→left sweep independently computes the minimum for the right-neighbor rule.
A child must satisfy both, so it needs at least the max of the two demands. That max is always achievable: setting a child’s candy to the larger demand still exceeds both neighbors, so neither rule breaks. Each directional value is already the smallest legal one, and max is the smallest value meeting two lower bounds at once, so the total is the global minimum. Equivalently, each child gets 1 + max(strictly-increasing run length ending at it from the left, run length from the right) — the least its position allows.
from typing import List
def candy(ratings: List[int]) -> int:
n = len(ratings)
candies = [1] * n
# left -> right: satisfy the left-neighbor rule
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# right -> left: satisfy the right-neighbor rule, keep the larger demand
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)
Walkthrough with ratings = [1, 3, 4, 5, 2]:
- Start:
[1, 1, 1, 1, 1].
- Left→right:
3>1→c[1]=2; 4>3→c[2]=3; 5>4→c[3]=4; 2>5? no. Now [1, 2, 3, 4, 1].
- Right→left:
5>2→c[3]=max(4, 1+1)=4; 4>5? no; 3>4? no; 1>3? no. Unchanged [1, 2, 3, 4, 1].
- Sum =
1+2+3+4+1 = 11.
Complexity: O(n) time (two linear sweeps), O(n) space for the candies array.
Approach 3 — One pass, O(1) space (slope counting)
The insight: you don’t need the whole candies array; you only need to account for up-slopes and down-slopes in the rating sequence. Walk once, tracking the length of the current increasing run (up) and decreasing run (down). Each up-run contributes 1+2+…+up, each down-run 1+2+…+down; a peak (the child at the top) is shared and counted with the longer of the two adjacent slopes. This is the arithmetic sum of the same values the two-pass method produces, computed on the fly.
from typing import List
def candy(ratings: List[int]) -> int:
n = len(ratings)
if n <= 1:
return n
total = 1 # first child gets 1
up = down = 0 # current increasing / decreasing run lengths
peak = 0 # candy given to the most recent peak
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
up += 1
down = 0
peak = up + 1
total += peak
elif ratings[i] == ratings[i - 1]:
up = down = 0
peak = 0
total += 1 # ties reset to the floor of 1
else:
up = 0
down += 1
# if the descent has grown past the peak, the peak needs one more
total += down + (1 if down >= peak else 0)
return total
Walkthrough with ratings = [1, 0, 2]:
total=1 for child 0.i=1: 0 < 1 → descent, down=1, peak=0; down >= peak so add 1 + 1 = 2 → total=3.i=2: 2 > 0 → ascent, up=1, peak=2; add peak = 2 → total=5.- Answer
5, matching candies [2, 1, 2].
Complexity: O(n) time, O(1) extra space. Same result as Approach 2 with no auxiliary array — the classic space-optimal form.
Common pitfalls
- Taking a sum instead of a max in the right→left sweep.
candies[i] = candies[i] + candies[i+1] + 1 over-allocates; the two directional demands overlap, so you want their max.
- Forgetting the right→left sweep entirely (or doing only one direction) — a child on a descending slope is constrained by its right neighbor, which a single left→right pass ignores.
- Mishandling equal ratings: ties impose no constraint, so a tie must let the candy count reset toward 1, not carry the previous run’s value forward.
- In the slope method, forgetting the peak adjustment when a descending run grows at least as long as the preceding ascending run — the peak then needs one extra candy to stay above the deepest descent.
Pattern takeaway
When a value is squeezed by constraints from two directions, resolve each direction with its own greedy sweep computing the local minimum, then combine with max so both are satisfied at once for the least cost. Decomposing a two-sided constraint into independent one-sided passes — then merging — is the reusable trick, and the arithmetic-series slope count is the standard way to shave the auxiliary array down to O(1) space.