hard

Candy

Hand out the fewest candies to children in a line so higher-rated children get more than their neighbors.

1. Define the problem

Candy

There are n children standing in a line, each assigned a rating value in the integer array ratings. You are giving candies to these children subject to two rules: every child must get at least one candy , and any child with a higher rating than a neighbor must get more candies than that neighbor. Return the minimum number of candies needed.

Constraints

  • n == ratings.length
  • 1 ≤ n ≤ 2 × 104
  • 0 ≤ ratingsi ≤ 2 × 104

Example

Inputratings = [1, 0, 2]
Output5

Explanation Give the children 2, 1, 2 candies respectively. That satisfies every neighbor rule using the fewest total candies.

2. Visualize the solution

Two passes: left to right, then right to left

Two passes: left to right, then right to left
Statusleft pass

Start: everyone gets 1 candy. candies = [1, 1, 1].

What happens in this step

candies = [1, 1, 1]  (one per child, before any comparisons)
ratings = [1, 0, 2]

Every child starts with exactly one candy; the left-to-right and right-to-left passes will only raise counts from here.
Step 1 of 5

Steps to visualize

  1. Give every child exactly one candy to start.
  2. Scan left to right: whenever a child's rating is higher than the child to their left, give them one more candy than that neighbor.
  3. Scan right to left: whenever a child's rating is higher than the child to their right, raise their candy count to at least one more than that neighbor's — never lower what the left pass already gave them.
  4. Sum every child's final candy count for the answer.
3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Two passes: left to right, then right to left
Statusleft pass

Start: everyone gets 1 candy. candies = [1, 1, 1].

What happens in this step

candies = [1, 1, 1]  (one per child, before any comparisons)
ratings = [1, 0, 2]

Every child starts with exactly one candy; the left-to-right and right-to-left passes will only raise counts from here.
Step 1 of 5
4. Solution

Solution

solution.tsTypeScript
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);
  }

  let total = 0;
  for (let i = 0; i < n; i++) total += candies[i];
  return total;
}
Time
O(n)
Space
O(n)
5. Test cases

Test cases

InputExpectedCovers
ratings = [1, 0, 2]5example from the docstring
ratings = [1, 2, 2]4equal ratings never require more candy than a neighbor
ratings = [5, 5, 5, 5]4all equal ratings — minimum, one candy each
ratings = [1, 2, 3, 4]10strictly increasing ratings
ratings = [4, 3, 2, 1]10strictly decreasing ratings needs the right-to-left pass
ratings = [7]1single child always gets exactly one candy
ratings = [3, 3]2two equal-rated children

Keep reading