Candy

Problem

n children stand in a line, each with a rating[i]. You must give each child at least 1 candy, and any child with a higher rating than an immediate neighbor must receive more candies than that neighbor. Return the minimum total candies needed. (LeetCode 135.)

Examples

Constraints

1 ≤ n ≤ 2·10⁴.

Attempt it first

This is the module's capstone because the constraint applies in both directions simultaneously — a child's candy count depends on comparisons with the neighbor to their LEFT and the neighbor to their RIGHT independently. Before opening anything, try to convince yourself of something specific: why can't a single left-to-right pass alone get this right? Construct (mentally or on paper) a small ratings array where a purely-left-to-right greedy assignment gives a WRONG answer because it never looked back after the fact to the right-side constraint, and think about what a second pass would need to do to fix it.