123. Candy

Satisfy the left neighbor rule and the right neighbor rule separately. First sweep left to right giving a child one more candy than its left neighbor when it's rated higher; then sweep right to left doing the same for the right neighbor, taking the maximum so both rules hold.

Idea

Each child's candy count must exceed both higher-rated neighbors. Handling both directions at once is tricky, so split it into two independent passes:

• Left→right: if ratings[i] > ratings[i-1], give candies[i] = candies[i-1] + 1. This satisfies every left neighbor constraint.
• Right→left: if ratings[i] > ratings[i+1], ensure candies[i] >= candies[i+1] + 1 (take the max so the left-pass result isn't lost).

After both passes every constraint holds with the minimum totals; sum them.

Algorithm

1. Start every child at 1 candy.
2. Left→right pass applying the left rule.
3. Right→left pass applying the right rule with max.
4. Return the sum.

Worked example: [1,0,2]

• Start [1,1,1]. Left→right: index 2 (2>0) → [1,1,2].
• Right→left: index 0 (1>0) → max(1,1+1)=2 → [2,1,2].

Sum = 5.

Complexity

• Time: O(n).
• Space: O(n).

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        for (int i = 0; i < n; i++) {
            candies[i] = 1;
        }
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }
        int total = 0;
        for (int c : candies) {
            total += c;
        }
        return total;
    }
}