Why it works
- The rule has two sides, and each pass settles one. Left to right, every child gets the fewest candies that satisfy the left neighbour, given what that neighbour already has.
- Right to left, max(candies[i], candies[i + 1] + 1) adds the right side without breaking the left one: a count only grows, and growing never hurts a child that must have more than its left neighbour.
- Each count is the length of the longest rising run that ends at the child, from the left or from the right, whichever is longer; no valid sharing can give less.
Complexity
Time O(n): two passes over the row. Memory O(n) for the candies.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗