10.1 Greedy

Demo: Candy — LC 135 (Hard — Google/Amazon High)

Statement (Demo): Children stand in a line with ratings. Give candies so that (1) every child gets at least one, and (2) a child with a higher rating than a neighbour gets more candies than that neighbour. Return the minimum total. Example: ratings=[1,0,2] → 5 (2, 1, 2) | ⚡ n ≤ 2×10⁴

Approach: Two passes — left→right: if the rating rises, give one more than the previous child; right→left: if the rating rises from the right, take the max to fix it. Both neighbour constraints are then satisfied.

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

Complexity: Time O(n), Space O(n)