Hard · Two Direction Greedy
Understand → Visualise → Practice.
Give every child at least one candy; a child rated above an adjacent child needs more. Return the minimum total.
One left-to-right pass fixes every 'rated higher than the left neighbour' rule; one right-to-left pass fixes the right-neighbour rule while keeping the left one by taking the maximum.
Start with candy = 1 for every child.
If ratings[i] > ratings[i − 1], set candy[i] = candy[i − 1] + 1.
If ratings[i] > ratings[i + 1], set candy[i] = max(candy[i], candy[i + 1] + 1); return the total.
O(n) time and O(n) space.
Overwriting instead of taking the maximum in the second pass breaks the rule fixed in the first pass.
Read the full guide first: Greedy Algorithms and Interval Patterns.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.