#159

Candy

hard

arraygreedy

n children stand in a line. Each child has a rating given by ratings[i]. You must hand out candies to every child so that:

- Every child receives at least one candy. - Any child whose rating is strictly greater than an immediate neighbor's rating must receive strictly more candies than that neighbor.

Return the minimum total number of candies you need to satisfy both rules.

Example

Input: ratings = [1,0,2]

Output: 5

Child 1 has the lowest rating and gets 1 candy. Both neighbors rate higher than child 1, so each needs at least 2. Total: 2 + 1 + 2 = 5.

Constraints

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

Intuition

A first pass starts everyone at 1 candy, then keeps re-scanning the line and bumping any child who breaks a neighbor rule, until a full scan makes no more changes.

function candy(ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1); // everyone starts at the floor of 1
  let changed = true;
  // Keep re-checking every neighbor rule until a full pass fixes nothing.
  while (changed) {
    changed = false;
    for (let i = 0; i < n; i++) {
      // Rule against the left neighbor.
      if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
        candies[i] = candies[i - 1] + 1;
        changed = true;
      }
      // Rule against the right neighbor.
      if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
        candies[i] = candies[i + 1] + 1;
        changed = true;
      }
    }
  }
  return candies.reduce((total, c) => total + c, 0);
}

Brute force — relax neighbor violations until nothing changes: O(n²).

This is O(n²) — a violation can only propagate one position per pass, so a long strictly-decreasing (or increasing) run needs a fresh full scan for every position in it before things stabilize. Can we do better?

The key observation: each child's requirement only ever depends on two fixed comparisons — "more than the left neighbor" and "more than the right neighbor." Neither direction needs to be re-checked once it's satisfied, so instead of relaxing repeatedly, satisfy each direction with one pass: sweep left-to-right so every child ranks correctly against its left neighbor, then sweep right-to-left so every child ranks correctly against its right neighbor too — taking the max of what both passes want, so the second pass never undoes what the first already secured. That's the Greedy chapter's two-pass local-constraint reconciliation technique: when a rule has to hold in both directions at once, one greedy pass can't see both sides, so run one pass per direction instead.

Walking it through:

ratings = [2, 4, 3, 1, 2, 5]

i↓

ratings[1]=4 > ratings[0]=2 → candies[1] = candies[0]+1 = 2

Left-to-right pass: child 1 outranks child 0, so it needs one more candy. Running total so far: [1, 2, _, _, _, _].

i↓

ratings[2]=3 not > ratings[1]=4 → candies[2] stays 1

Child 2 rates lower than child 1, so the left pass leaves it at the floor of 1 — even though child 2 also outranks child 3, a direction this pass can't see yet.

i↓

ratings[5]=5 > ratings[4]=2 → candies[5] = candies[4]+1 = 3

Left pass complete: [1, 2, 1, 1, 2, 3]. Every 'higher than the left neighbor' rule holds, but child 2 (rating 3) still sits at 1 despite outranking child 3 (rating 1).

i↓

ratings[2]=3 > ratings[3]=1 → candies[2] = max(1, candies[3]+1) = max(1, 2) = 2

Right-to-left pass: children 4 and 3 were already swept (neither outranks its right neighbor, so neither changed) before reaching child 2, which outranks child 3 and needs more than its 1. The max keeps the left pass's work intact — candies[2] rises from 1 to 2.

i↓

ratings[1]=4 > ratings[2]=3 → candies[1] = max(2, candies[2]+1) = max(2, 3) = 3

Child 1 is the peak, outranking both neighbors. The left pass already gave it 2; the right pass now demands one more than child 2's updated 2, so it climbs again to 3.

i↓

sum([1, 3, 2, 1, 2, 3]) = 12

Right pass complete: [1, 3, 2, 1, 2, 3]. Every neighbor rule holds in both directions — the minimum total is 12 candies.

Optimization

Two-pass greedy

Start every child with 1 candy. Sweep left to right: whenever a child rates higher than the child to their left, give them one more candy than that neighbor. This satisfies every "higher than the left neighbor" constraint, but may still shortchange a child who rates higher than their right neighbor.

Sweep right to left to fix that: whenever a child rates higher than the child to their right, they need at least one more candy than that neighbor — but take the max with whatever the left-to-right pass already gave them, since the left pass may have already assigned something bigger.

Sum the per-child candy counts for the answer. O(n) time, O(n) space for the candies array.

function candy(ratings) {
  const n = ratings.length;
  // Everyone starts at the floor of 1 candy.
  const candies = new Array(n).fill(1);

  // Left-to-right pass: satisfy "more than the left neighbor" in one sweep.
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }

  // Right-to-left pass: satisfy "more than the right neighbor" too, taking
  // the max so this pass never undoes what the left pass already secured.
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      candies[i] = Math.max(candies[i], candies[i + 1] + 1);
    }
  }

  // Total candies handed out across every child.
  return candies.reduce((total, c) => total + c, 0);
}

Complexity analysis

Time complexity: O(n). Here's why:

The left-to-right pass visits each of the n children once, doing O(1) work per child.
The right-to-left pass does the same, visiting each child once more.

Two linear passes back to back is still O(n) — a fixed constant factor of two passes, not the brute force's repeated re-scanning.

Space complexity: O(n). Here's why:

The candies array holds one entry per child — O(n) auxiliary space.
Both passes otherwise only keep a loop index and a couple of comparisons — O(1) beyond that array.

So the overall auxiliary space is O(n), dominated by the candies array itself.

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
ratings = [9]	1	Single child — always exactly 1 candy, regardless of rating.
ratings = [6,6,6,6,6]	5	All-equal ratings — no strict difference anywhere, so every child stays at the floor of 1.
ratings = [1,2,2,1]	6	A tied plateau in the middle — ties impose no ordering, so no bonus candy is forced across them.
ratings = [1,1,5,1,1]	6	An isolated peak surrounded by flat ground on both sides — only the peak itself needs extra candy.
ratings = [5,3,1,3,5]	11	A valley between two peaks — exercises the right-to-left pass overriding what the left pass gave both peaks.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor