Candy

hard array greedy two pass

Problem

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy.

Inputratings = [1, 0, 2]

Output5

Candies become [2, 1, 2]. Total = 5.

ratings (comma-separated)

def candy(ratings):
    n = len(ratings)
    c = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            c[i] = c[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            c[i] = max(c[i], c[i + 1] + 1)
    return sum(c)

function candy(ratings) {
  const n = ratings.length;
  const c = new Array(n).fill(1);
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1;
  }
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
  }
  return c.reduce((s, x) => s + x, 0);
}

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

int candy(vector<int>& ratings) {
    int n = ratings.size();
    vector<int> c(n, 1);
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) c[i] = max(c[i], c[i + 1] + 1);
    }
    int total = 0;
    for (int x : c) total += x;
    return total;
}

Explanation

Every child needs at least one candy, and a child with a higher rating than a neighbor must get more candies than that neighbor. The clean trick is to satisfy the left side and right side separately with two passes, then combine them.

Start everyone at 1 candy. In a left-to-right pass, whenever ratings[i] > ratings[i-1], give child i one more than its left neighbor: c[i] = c[i-1] + 1. This handles all the rising slopes going right.

Then in a right-to-left pass, whenever ratings[i] > ratings[i+1], set c[i] = max(c[i], c[i+1] + 1). The max is crucial: it keeps the candy count already earned from the first pass while also satisfying the right neighbor. The answer is the sum of c.

Example: ratings = [1, 0, 2]. Left pass gives [1, 1, 2]. Right pass bumps index 0 (rating 1 > 0) to max(1, 1+1) = 2, giving [2, 1, 2]. The total is 5.

Time: O(n) Space: O(n)