Candy
Hard · Greedy · Array · Greedy
Problem
n children stand in a row, and child i has a rating ratings[i]. You hand out candies under two rules:
- every child receives at least one candy;
- a child with a strictly higher rating than an adjacent child must receive more candies than that neighbor.
Children with equal ratings impose no rule on each other. Return the minimum total number of candies needed.
Examples
Input: ratings = [1,3,2,1] Output: 7
Give 1, 3, 2, 1 candies. The 3 must beat the 2, which must beat the 1.
Input: ratings = [2,2,2] Output: 3
Equal neighbors impose nothing, so each child gets one.
Input: ratings = [1,2,3,1] Output: 7
Give 1, 2, 3, 1 candies.
Constraints
- n == len(ratings)
- 1 <= n <= 2 · 10^4
- 0 <= ratings[i] <= 2 · 10^4
Approaches
- Baseline: raise counts until nothing changes — time O(n²), space O(n)
Follow-up
What if the children sit in a circle? A lowest-rated child always gets exactly one candy, so cut the ring there and the two passes still work. See the use case “Children in a circle”.
Related problems
Start free on Cariara · Coding problems · System design studio
