Candy

Problem

A teacher lines children up by rating and hands out candies under a fairness rule: every child gets at least one candy, and any child rated strictly higher than an adjacent child must receive strictly more candies than that neighbor. Ratings may rise, fall, or repeat arbitrarily. Compute the minimum total number of candies that satisfies every child.

Example 1:

Input: ratings = [3, 7, 5, 2, 8]
Output: 9
Explanation: candy per child [1, 3, 2, 1, 2] - 7 tops both neighbors, 8 tops its left neighbor, and the valley at 2 keeps the minimum.

Example 2:

Input: ratings = [5, 5, 5, 5]
Output: 4
Explanation: equal neighbors constrain nothing; one candy each is already fair.

Example 3:

Input: ratings = [2, 4, 6, 8]
Output: 10
Explanation: strictly rising ratings force the staircase 1 + 2 + 3 + 4.

Constraints:

• 1 <= ratings.length <= 2 * 10^4
• 0 <= ratings[i] <= 2 * 10^4

Solution Breakdown

Approach - decompose the pairwise constraints by direction, satisfy each with its own sweep, and merge with an element-wise max.

Every constraint points one way: "I beat my left neighbor" or "I beat my right neighbor." A left-to-right sweep can fully satisfy the first family - whenever ratings[i] > ratings[i-1], hand the child exactly give[i-1] + 1, the smallest value that keeps the promise; everyone else stays at the minimum 1. The right-facing family is where single-pass approaches die: the cost of a falling run is discovered only from its end, and the child at a peak may need a value proportional to the entire descending chain to its right. So a second sweep runs right-to-left, and whenever ratings[i] > ratings[i+1] it raises give[i] - crucially to max(give[i], give[i+1] + 1), not a plain assignment, because a peak child carries obligations on both sides and the max is what keeps the left promise intact while adding the right one. After both sweeps every directed constraint holds, and the assignment is also minimal: each child's final count is exactly the length of the longest chain forcing it - any valid assignment must dominate those values position by position, so no smaller total exists.

Trace [3, 7, 5, 2, 8]: the left pass produces [1, 2, 1, 1, 2] (7 rises over 3, 8 rises over 2). The right pass walks back: 8 is unconstrained from its right (nothing follows), 2 stays 1; 5 > 2 lifts the 5 to 2; 7 > 5 lifts 7 to max(2, 2+1) = 3; 3 is unconstrained from its right and keeps 1. Final [1, 3, 2, 1, 2], sum 9 - the peak at 7 paid for both slopes, the valley at 2 kept the minimum.

Edge cases - all-equal ratings trigger no rule, so the answer is n (one per child); a single child takes 1; strictly increasing rows are the pure staircase 1 + 2 + ... + n with the right pass inert; valleys (local minima) are never raised by either pass - [9, 3, 6] leaves the 3 at exactly 1 while both sides rise to 2, totaling 5.

Complexity - O(n) time, two linear sweeps with constant work each; O(n) space for the give array - the right pass reads give[i+1] after earlier writes, so the counts cannot be folded into a running sum without losing the left-pass information.