first pass left to right: if rating[i] > rating[i-1], give one more candy than previous. second pass right to left: if rating[i] > rating[i+1], ensure we have more than next.
take maximum of both passes to satisfy both left and right constraints. start with 1 candy for each child.
approach
- initialize all with 1 candy
- left pass: handle increasing sequences
- right pass: handle decreasing sequences
- take max to satisfy both directions
complexity
O(n) time for two passes, O(n) space for candy array. optimal greedy solution.