Candy

GREEDY · HARD

Builds on Day 27: Greedy Algorithms

Read that lesson first if “make the locally-best choice and trust it holds up globally” is still a new idea.

The problem

n children stand in a line. Each child has a rating. You must hand out candies so that: every child gets at least 1 candy, and any child with a higher rating than an immediate neighbor gets strictly more candies than that neighbor. Return the minimum total number of candies that satisfies both rules for every child.

The trap is that “higher rating → more candy” is a local, pairwise rule, but it has to hold simultaneously in both directions at once — against the child on the left AND the child on the right — for every single child in the line.

Solution 1: Brute force — start at 1, repeatedly re-scan and fix violations

Give every child 1 candy to start. Then keep re-scanning the whole line, left to right, fixing any child whose candy count still violates a neighbor rule (bump them to one more than whichever neighbor they’re violating against). Keep re-scanning from the top until one full pass makes zero fixes. This is correct — a fix can only ever increase a count, and counts are bounded, so it’s guaranteed to terminate — but a single fix on one side of the line can force another fix several children away, which then needs its own pass to propagate further. Worst case (e.g. a long strictly-increasing-then-strictly-decreasing run), the fix has to ripple one child further per pass, so it converges slowly.

Interactive visualization

ratings = [1, 3, 2, 2, 1, 4] — brute force re-scans, fixing until stable

Press Play or Step to begin.

Step 0 / 17

▶ Play↺ Reset

The code

function candyBruteForce(ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1);
  let changed = true;
  while (changed) {
    changed = false;
    for (let i = 0; i < n; i++) {
      if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {
        candies[i] = candies[i - 1] + 1;
        changed = true;
      }
      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((sum, c) => sum + c, 0);
}

Line by line:

• new Array(n).fill(1) — every child starts at the minimum legal amount.
• The outer while (changed) loop keeps re-scanning until a complete pass over every index makes zero fixes — that’s the stopping condition, not a fixed number of passes.
• The first if checks the left neighbor: if this child rates higher than the child to their left but doesn’t yet have strictly more candy, bump them to candies[i-1] + 1.
• The second if does the same check against the right neighbor. Both checks run on every index every pass — a child can need fixing against either side, or both.
• Because a fix in one spot can only be discovered as necessary after a neighboring fix already landed (on a previous or even the same pass), violations can require several passes to fully settle.

Complexity

Time	Space	Approach
Repeated re-scans until stable (qualitatively worse than O(n) — each pass is O(n), and a chain of violations can force roughly one extra pass per additional child in the chain, so it converges slowly on long monotonic runs)	O(n)	Start at 1, re-scan + fix until no pass makes changes

Solution 2: Optimal — two linear passes, no re-scanning

The key insight: a child’s final candy count only ever depends on one direction at a time if you handle the directions separately. Pass left→right and only enforce “beats the left neighbor”. Pass right→left and only enforce “beats the right neighbor”, taking the max with whatever the left pass already gave that child so neither pass undoes the other’s work. Both constraints end up satisfied after exactly two passes — no re-scanning, no rippling.

Interactive visualization

ratings = [1, 3, 2, 2, 1, 4] — two clean passes, no re-scanning

Press Play or Step to begin.

Step 0 / 15

▶ Play↺ Reset

The code

function candyOptimal(ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1);

  // Pass 1: left → right — only the left-neighbor rule.
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1;
    }
  }

  // Pass 2: right → left — only the right-neighbor rule, via max().
  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((sum, c) => sum + c, 0);
}

Line by line:

• new Array(n).fill(1) — same baseline as brute force: everyone starts legal.
• Pass 1 only ever looks left (ratings[i] > ratings[i-1]). By the time it reaches index i, index i-1 is already finished for this pass, so the whole left-side constraint is nailed in one clean sweep.
• Pass 2 only ever looks right (ratings[i] > ratings[i+1]), walking backward so i+1 is already finished.
• Math.max(candies[i], candies[i + 1] + 1) is the crux: pass 1 may have already given candies[i] a big value satisfying the left rule. Pass 2 must not shrink that — it can only raise the count further if the right rule demands more.
• candies.reduce((sum, c) => sum + c, 0) — the answer is just the total candy count once both constraints hold everywhere at once.

Complexity

Time	Space	Approach
O(n)	O(n)	Two linear passes, one direction enforced per pass

Complexity comparison

Solution	Time	Space
Brute force (re-scan + fix until stable)	Repeated O(n) passes — converges slowly on long runs, qualitatively worse than linear	O(n)
Optimal (two-pass greedy)	O(n)	O(n)

Interview corner

Why does doing one pass left-to-right and one pass right-to-left actually satisfy BOTH neighbor constraints at once, for every child?

• Each pass only ever writes based on comparing against a neighbor whose value for that pass is already finalized — pass 1 never looks right, pass 2 never looks left.
• Pass 1 alone guarantees “beats a higher-rated left neighbor” holds everywhere.
• Pass 2’s max() guarantees “beats a higher-rated right neighbor” holds everywhere, without ever undoing what pass 1 already proved for the left side.
• Since neither pass can lower a count, both proofs survive to the end — the final array satisfies both directions simultaneously.

Why Math.max(candies[i], candies[i + 1] + 1) in pass 2, instead of just candies[i] = candies[i + 1] + 1?

• Without max, pass 2 would blindly overwrite whatever pass 1 computed.
• Example: ratings [1, 3, 2] — pass 1 gives index 1 two candies (beats the left neighbor). Index 1 doesn’t need fixing in pass 2 at all (3 > 2 is false the other way — index 1’s rating isn’t > ratings[2]).
• But in general, a plain overwrite risks shrinking a count that pass 1 legitimately earned, silently breaking the left-side guarantee that pass 1 just established.
• ⚠ Trap: it’s tempting to think “later pass wins” the way state updates often work — here the later pass must only ever raise the value, never simply replace it.

Two adjacent children have the EQUAL ratings — does either need extra candy?

• No. The rule is “strictly higher rating → strictly more candy” — equal ratings carry no ordering requirement between those two children at all.
• Both conditions use strict >, never >=, so a plateau of equal ratings never triggers a bump between those neighbors.
• Each child in a plateau can independently sit at whatever its own left/right constraints (from its OTHER neighbor) require — often just the baseline of 1.

Trick question — what does this log?

const candies = [];
console.log(candies.reduce((sum, c) => sum + c));

• Answer: it throws — TypeError: Reduce of empty array with no initial value. Nothing is logged; the program crashes at that line.
• .reduce() without a second argument uses the array’s first element as the starting accumulator. An empty array has no first element, so there’s nothing to start from.
• This is exactly why both solutions above call candies.reduce((sum, c) => sum + c, 0) with an explicit 0 — that initial value makes the reduce safe even in principle, regardless of array length.
• ⚠ Trap: LeetCode guarantees n >= 1 here so candies is never actually empty in this problem — but the moment this summing logic gets copy-pasted into different code without that guarantee, omitting the 0 becomes a live crash waiting to happen.

Quiz

Quiz: 1. Why is it enough to make just ONE left-to-right pass and ONE right-to-left pass, instead of repeatedly re-scanning like brute force?

Each pass only enforces one neighbor direction using already-finalized values, so one pass per direction is provably sufficient

Each pass enforces exactly one neighbor direction using only information that pass has already finalized (pass 1 never looks right, pass 2 never looks left), so by the end of pass 2 both directions are proven correct at once — no re-scanning needed.

Quiz: 2. What would go wrong if pass 2 used a plain assignment (candies[i] = candies[i+1] + 1) instead of Math.max(candies[i], candies[i+1] + 1)?

It could shrink a count pass 1 already earned, breaking the left-neighbor guarantee pass 1 just proved

Pass 1 already proved the left-neighbor rule for every child. Pass 2’s max() lets it raise a count further for the right-neighbor rule, but never lets it shrink a count and silently break what pass 1 already established.

Quiz: 3. Why don’t two adjacent children with the SAME rating ever need different candy counts because of each other?

Every comparison uses strict > — equal ratings never trigger a bump between those two neighbors

Both the brute-force checks and the optimal passes use strict greater-than (>), so a plateau of equal ratings never forces either neighbor to get more candy than the other.

Quiz: 4. Why can brute force need MANY passes on a long strictly-increasing (or decreasing) run of ratings, instead of settling in one or two?

A fix can only be discovered as needed after a neighboring fix already landed, so violations ripple roughly one child further per pass

Brute force fixes one violated neighbor pair at a time, and a fix can only be recognized as needed after the neighbor that causes it has already been fixed — on a long strictly increasing or decreasing run, that forces roughly one extra pass per additional child before the whole line stabilizes.

Quiz: 5. What’s the honest complexity difference between the two solutions?

Optimal is a fixed O(n) (two passes); brute force repeats O(n) passes an input-dependent number of times, converging slowly on long runs

Optimal is a clean O(n): exactly two passes, each touching every child once. Brute force’s total work isn’t a fixed small multiple of n — the number of full re-scans needed can grow with how long the monotonic runs in the input are, so it’s qualitatively slower even though a single pass of it is also O(n).