Approach Summary
Two passes: give more candy to each child with a higher rating than their left neighbour, then right. Take the max at each position.
How to Recognize This Pattern
- Satisfy left and right constraints separately
- Two greedy sweeps — left rule and right rule independently
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
Tags
Array Greedy