Loading…

hardArraysLC #135Sometimes asked

Candy

LCPractice

Two Pointers · 13 of 30 · 10 min

There are n children standing in a line, each assigned a rating value given in the integer array ratings.

You are giving candies to these children subject to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

In plain English

Give each child at least one candy, and strictly more than any adjacent child with a lower rating — in BOTH directions. Equal-rated neighbors have no relationship. Minimize the total. The constraint couples each child to its left and right neighbor, which is why one sweep can't do it.

Examples

Example 1

Input: ratings = [1,0,2]
Output: 5
Note: Candies [2,1,2]: child 0 (rating 1) > child 1 (rating 0); child 2 (rating 2) > child 1. Total 5.

Example 2

Input: ratings = [1,2,2]
Output: 4
Note: Candies [1,2,1]: child 1 > child 0. Children 1 and 2 are equal-rated, so no constraint — child 2 can drop back to 1. Total 4.

Example 3

Input: ratings = [1,3,2,2,1]
Output: 7
Note: Candies [1,2,1,2,1]: the peak at index 1 beats its left; the descent 2,2,1 is handled by the right pass. Total 7.

Constraints

n == ratings.length
1 ≤ n ≤ 2 × 10⁴
0 ≤ ratings[i] ≤ 2 × 10⁴

Clarifying questions4First question: Does the 'more than neighbors' rule apply to both the left and right neighbor?Explore questions

Q1.Does the 'more than neighbors' rule apply to both the left and right neighbor?
Yes — a child with a higher rating than EITHER neighbor must out-candy that neighbor. That two-sided coupling is exactly why we need two passes.
Q2.What happens when two adjacent children have equal ratings?
No constraint between them. They can have any candy counts (each still ≥ 1). This is the detail that keeps it from being a strict monotonic assignment.
Q3.Do I need to return the assignment or just the total?
Just the minimum total count. The per-child assignment is computed internally but only the sum is returned.
Q4.Is there always a valid distribution?
Yes — giving everyone 1 already satisfies the floor, and the passes only ever increase counts, so a valid (and minimal) solution always exists.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Each child needs ≥ 1 candy, and a child with a higher rating than a neighbor must get more than that neighbor. The clean answer is two greedy passes: left-to-right enforce the 'greater than left neighbor' rule, then right-to-left enforce 'greater than right neighbor' while taking the max of the two demands. Summing the per-child maxima gives the minimum total. O(n) time, O(n) space (an O(1)-space one-pass exists).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that a both-neighbors constraint decomposes into two independent one-directional passes, and whether you correctly combine them with max instead of overwriting.

Where candidates slip

Trying to solve it in a single pass (you can't satisfy both neighbors at once), or overwriting instead of taking max on the right pass — which breaks the left-neighbor guarantee.

How to stand out

State the decomposition explicitly (left rule, right rule, reconcile with max), prove minimality, and offer the O(1)-space one-pass slope-counting solution as the follow-up.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Two Passes (Left→Right then Right→Left)	`O(n)`	`O(n)`	The answer they want. Lead with the decomposition insight: a both-neighbors rule = a left rule + a right rule, reconciled with max.	Read
2	One Pass, O(1) Space (Slope Counting)Optimal	`O(n)`	`O(1)`	Offer when asked to remove the O(n) array. It tracks ascending/descending run lengths instead of storing per-child candy. Harder to get right — only attempt it if you can explain the peak adjustment.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Decomposing the two-sided constraint

How to read it:One pass per direction, reconciled by max. The two-pass greedy is the standard answer.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Two Passes (Left→Right then Right→Left)

TimeO(n)SpaceO(n)

The answer they want. Lead with the decomposition insight: a both-neighbors rule = a left rule + a right rule, reconciled with max.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A child must beat BOTH neighbors when it's rated higher. Can one left-to-right pass ever know about the neighbor to its right? What does that suggest about how many passes you need?

2Hint 2Explore hint

Pass 1 (left→right): give everyone 1, then whenever ratings[i] > ratings[i-1], set candy[i] = candy[i-1] + 1. This satisfies every left-neighbor constraint.

3Hint 3Explore hint

Pass 2 (right→left): whenever ratings[i] > ratings[i+1], set candy[i] = max(candy[i], candy[i+1] + 1). The max preserves pass 1's work while adding the right-neighbor guarantee.

A · Core idea

The constraint 'a higher-rated child gets more candy than its neighbors' is two-sided: it talks about the left neighbor and the right neighbor simultaneously. A single left-to-right scan structurally cannot satisfy it, because when you assign candy[i] you haven't yet seen candy[i+1]. The key insight is to split the two-sided rule into two one-sided rules and handle each with its own directional pass.

Pass 1 — satisfy the left neighbor. Initialize every child to 1 (the floor). Sweep left to right; whenever ratings[i] > ratings[i-1], the current child outranks the one on its left, so it must have strictly more: set candy[i] = candy[i-1] + 1. After this pass, every 'greater than left neighbor' constraint holds, and ascending runs get the staircase 1,2,3,… they require. What's not yet handled: a child that should beat its right neighbor (the descending side of a peak).

Pass 2 — satisfy the right neighbor, without breaking pass 1. Sweep right to left; whenever ratings[i] > ratings[i+1], the child must out-candy its right neighbor, demanding at least candy[i+1] + 1. Here is the crucial move: we write `candy[i] = max(candy[i], candy[i+1] + 1)`, not a plain assignment. The max is what makes the two passes compose. candy[i] already encodes the left-neighbor requirement from pass 1; the right pass only raises it if the right-neighbor requirement is stronger. Overwriting instead would discard the left guarantee and produce an invalid distribution at peaks that tower over both sides.

Why the result is minimal. Every increment we perform is forced: we only ever bump a child to exactly one more than the neighbor that forces it, and we take the smaller value that still satisfies both sides (max of two tight lower bounds is itself the tight lower bound). No child is ever larger than it must be, so the sum is the minimum. A child sitting at a peak ends up at max(leftRun, rightRun) + 1, which is precisely the smallest value exceeding both descending/ascending slopes — exactly right.

Why equal ratings need no special handling. When ratings[i] == ratings[i-1], neither > test fires, so neither pass raises the child on account of that neighbor. It stays at whatever the other side demands (often back down to 1), which is why [1,2,2] correctly yields [1,2,1] rather than forcing the second 2 upward.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

ratings = [1,0,2]

Array state

init

all 1

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final resultsum([2,1,2]) = 5

C · Code with teaching comments

Reference implementation previewpublic int candy(int[] ratings) { int n = ratings.length; int[] candy = new int[n]; Arrays.fill(candy, 1); for (int i = 1; i < n; i++) {Explore the full code

solution.javaJava

Two Passes (Left→Right then Right→Left) — reference

4 teaching notes

1
public int candy(int[] ratings) {
2
    int n = ratings.length;
3
    int[] candy = new int[n];
4
    // Everyone starts at the floor of 1 candy.
5
    Arrays.fill(candy, 1);
6
    for (int i = 1; i < n; i++) {
7
        if (ratings[i] > ratings[i - 1]) {
8
            candy[i] = candy[i - 1] + 1;
9
        }
10
    }
11
    for (int i = n - 2; i >= 0; i--) {
12
        if (ratings[i] > ratings[i + 1]) {
13
            // Right pass: raise only if the right-neighbor demand exceeds pass 1's
14
            // value.
15
            candy[i] = Math.max(candy[i], candy[i + 1] + 1);
16
        }
17
    }
18
    int total = 0;
19
    // Sum the minimal per-child counts.
20
    for (int c : candy) total += c;
21
    return total;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

A constraint that references both neighbors decomposes into two independent single-direction constraints. Solve each with a directional sweep, then reconcile per element with max. The max is the linchpin — it lets the second pass strengthen the first without erasing it.

ComplexityO(n) time, O(n) space — Two linear passes → O(n) time. A candy[] array of size n → O(n) space.

E · Edge cases and pitfalls6ratings = [1] — Single child → candy [1] → total 1.Explore edge cases

Edge cases handled

ratings = [1]Single child → candy [1] → total 1.
ratings = [2,2,2]All equal, no constraint fires → [1,1,1] → total 3.
ratings = [1,2,3,4,5]Strictly increasing → left pass gives [1,2,3,4,5]; right pass no-op → total 15.

Pitfalls

Overwriting instead of max on the right pass — destroys the left-neighbor guarantee at peaks.
Using >= instead of > — equal ratings impose no constraint; >= over-allocates.
Doing only one pass — leaves every right-side descent under-allocated.

03.2

Approach 2 of 2 · Optimal

One Pass, O(1) Space (Slope Counting)

TimeO(n)SpaceO(1)

Offer when asked to remove the O(n) array. It tracks ascending/descending run lengths instead of storing per-child candy. Harder to get right — only attempt it if you can explain the peak adjustment.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't actually need the whole candy array — only the running length of the current ascending run and descending run.

2Hint 2Explore hint

On an increase, extend the up-run and add its new length. On a decrease, extend the down-run and add its length.

3Hint 3Explore hint

The peak between an up-run and a down-run is shared; when the down-run hasn't yet exceeded the up-run's height, you've counted the peak twice and must subtract one.

A · Core idea

The two-pass method stores a candy count per child, costing O(n) memory. But the only thing that determines a child's candy is the length of the monotonic run it sits in. Tracking those run lengths lets us accumulate the total in one pass without the array.

The counters. Walk left to right maintaining up (length of the current strictly-increasing run), down (length of the current strictly-decreasing run), and peak (the up value captured at the most recent peak). Start the total at n — that pre-pays the floor of one candy for everyone, so each addition below represents only the extra candies beyond the floor.

Rising. When ratings[i] > ratings[i-1], we're climbing: increment up, reset down = 0, and record peak = up. The climber needs up more candies than the valley it started from, so add up to the total. (A staircase 1,2,3 adds 0+1+2 extra over the floor — correct.)

Falling. When ratings[i] < ratings[i-1], we're descending: increment down, reset up = 0, and add down. Giving the descending children 1,2,3,… from the bottom up keeps each strictly above its right neighbor. The subtlety: the peak at the top of the descent is shared between the up-run and the down-run. While the descent is still shorter than or equal to the peak's height (peak >= down), the peak is already tall enough to dominate the descent, and our += down has implicitly counted the peak once too often — so we subtract 1. Once the descent grows longer than the peak (down > peak), the peak genuinely must be raised to stay above the lengthening descent, and the += down correctly performs that raise without subtraction.

Flat. When ratings are equal, all runs reset to 0 and nothing is added beyond the already-counted floor — matching the 'no constraint between equals' rule.

Why two-pass is still the better interview answer. This one-pass version is provably equivalent and saves memory, but its correctness rests on the peak-sharing adjustment that's easy to bungle under pressure. Unless the interviewer explicitly demands O(1) space, present the two-pass solution (whose minimality is transparent) and mention this as the optimization you'd reach for when memory is tight.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

ratings = [1,2,3,1,0]

Interactive diagram

Decomposing the two-sided constraint

i=1 (2>1)

Active call / nodeSupporting contextReturned stateNot active

One pass per direction, reconciled by max. The two-pass greedy is the standard answer.

Final result9 (candy would be [1,2,3,2,1])

C · Code with teaching comments

solution.javaJava

One Pass, O(1) Space (Slope Counting) — optimal

4 teaching notes

1
public int candy(int[] ratings) {
2
    int n = ratings.length;
3
    if (n <= 1) return n;
4
    // Pre-pay the floor of one candy per child; additions below are the extras.
5
    int total = n;
6
    int up = 0, down = 0, peak = 0;
7
    for (int i = 1; i < n; i++) {
8
        if (ratings[i] > ratings[i - 1]) {
9
            up++;
10
            down = 0;
11
            peak = up;
12
            total += up;
13
        } else if (ratings[i] == ratings[i - 1]) {
14
            up = 0;
15
            down = 0;
16
            peak = 0;
17
        } else {
18
            up = 0;
19
            down++;
20
            total += down;
21
            if (peak >= down) {
22
                total--;
23
            }
24
        }
25
    }
26
    return total;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

A child's candy is fully determined by the length of the monotonic run it belongs to, so you can sum the total from run-length counters alone. The only trap is the shared peak between an ascent and a descent — subtract one until the descent outgrows the ascent.

ComplexityO(n) time, O(1) space — A single left-to-right pass with a handful of integer counters → O(n) time, O(1) extra space (no candy array).

E · Edge cases and pitfalls6ratings = [5,4,3,2,1] — All descending, peak stays 0 so no subtraction → total 5+1+2+3+4 = 15.Explore edge cases

Edge cases handled

ratings = [5,4,3,2,1]All descending, peak stays 0 so no subtraction → total 5+1+2+3+4 = 15.
ratings = [1,2,2]i=1 up=1 total→4; i=2 equal resets → total 4.
ratings = [2]n ≤ 1 short-circuit → 1.

Pitfalls

Forgetting to reset down (and peak) when a new ascent starts — leaks stale run lengths.
Subtracting unconditionally on every descent instead of only while peak >= down — under-counts long descents.
Not resetting runs on equal ratings — treats a flat as part of a slope.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int candy(int[] ratings) { int n = ratings.length; if (n <= 1) return n; int total = n; int up = 0, down = 0, peak = 0;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Overwriting instead of taking max on the right pass

At a peak that beats both neighbors, the left pass already set a large value. A plain assignment on the right pass discards it, so the peak may end up ≤ its left neighbor — invalid.

Explore the code comparison

Don't write this

for (int i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
        candy[i] = candy[i + 1] + 1;
    }
}

Write this instead

for (int i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
        candy[i] = Math.max(candy[i], candy[i + 1] + 1);
    }
}

Using >= and over-allocating on equal ratings

Equal-rated neighbors have NO ordering constraint. Using >= forces a strict increase that isn't required, inflating the total (e.g. [1,2,2] would wrongly cost 5 instead of 4).

Explore the code comparison

Don't write this

if ratings[i] >= ratings[i - 1]:
    candy[i] = candy[i - 1] + 1

Write this instead

if ratings[i] > ratings[i - 1]:
    candy[i] = candy[i - 1] + 1

Solving it in one greedy pass

A single left-to-right pass can't see the right neighbor, so descents after a peak get only 1 candy and violate the rule. You need a second pass (or run-length tracking) to handle the other direction.

Explore the code comparison

Don't write this

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

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two greedy sweeps (left→right, right→left, take max)

Code pattern to memorize

candy = [1]*n
for i in 1..n-1:
    if r[i] > r[i-1]: candy[i] = candy[i-1] + 1
for i in n-2..0:
    if r[i] > r[i+1]: candy[i] = max(candy[i], candy[i+1] + 1)
return sum(candy)

Rules to remember

1Start everyone at 1 — that satisfies the 'at least one candy' floor.
2Left pass fixes the left-neighbor constraint; right pass fixes the right-neighbor constraint.
3On the right pass, take the max — never overwrite the left pass's result, or you break one side.
4Equal ratings impose no constraint — neighbors with the same rating may differ freely in candy.
5One constraint per direction means one pass per direction; a single pass can't see both neighbors at once.

Use this pattern when

Assign values under local neighbor constraints in both directions
Minimize a total subject to 'strictly greater than smaller neighbor'
Any 1-D problem where each element depends on left AND right context
Slope/peak-valley reasoning over a sequence

Choose another pattern when

Constraint is only one-directional → a single pass suffices
Constraint is non-local (depends on all elements) → not a sweep; think DP or sorting
You need the assignment to be unique → this yields the minimum, not the only valid one
Ratings form a 2-D grid → BFS/DP by value order, not a linear sweep

Interview takeaway

Two-directional local constraints split into two one-directional sweeps whose results you combine with max. Candy is the archetype: decompose a 'both neighbors' rule into a left pass and a right pass, then reconcile. The same decomposition powers Trapping Rain Water and Product of Array Except Self.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternTwo-directional local constraint solved by a left pass + a right pass reconciled with max (with an O(1) slope-counting one-pass variant). Recognise it whenever each element's value depends on both its neighbors. Same decomposition as Trapping Rain Water and Product of Array Except Self.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Trapping Rain Water
Same two-directional decomposition: each bar's water depends on the max height to its left AND right.
Product of Array Except Self
Prefix pass times suffix pass — combine two directional sweeps into a per-element answer.
Container With Most Water
Two-pointer greedy where each move is justified by which side limits the area.
Partition Labels
Coming soon
Greedy sweep using a precomputed 'last occurrence' to extend partitions — single-direction cousin.

Same pattern

←

Best Time to Buy and Sell Stock II

Continue · Next problem

H-Index

hardArraysLC #135Sometimes asked

Candy

LCPractice

Two Pointers · 13 of 30 · 10 min

There are n children standing in a line, each assigned a rating value given in the integer array ratings.

You are giving candies to these children subject to the following requirements:

Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

In plain English

Examples

Example 1

Input: ratings = [1,0,2]
Output: 5
Note: Candies [2,1,2]: child 0 (rating 1) > child 1 (rating 0); child 2 (rating 2) > child 1. Total 5.

Example 2

Input: ratings = [1,2,2]
Output: 4
Note: Candies [1,2,1]: child 1 > child 0. Children 1 and 2 are equal-rated, so no constraint — child 2 can drop back to 1. Total 4.

Example 3

Input: ratings = [1,3,2,2,1]
Output: 7
Note: Candies [1,2,1,2,1]: the peak at index 1 beats its left; the descent 2,2,1 is handled by the right pass. Total 7.

Constraints

n == ratings.length
1 ≤ n ≤ 2 × 10⁴
0 ≤ ratings[i] ≤ 2 × 10⁴

Clarifying questions4First question: Does the 'more than neighbors' rule apply to both the left and right neighbor?Explore questions

Q1.Does the 'more than neighbors' rule apply to both the left and right neighbor?
Yes — a child with a higher rating than EITHER neighbor must out-candy that neighbor. That two-sided coupling is exactly why we need two passes.
Q2.What happens when two adjacent children have equal ratings?
No constraint between them. They can have any candy counts (each still ≥ 1). This is the detail that keeps it from being a strict monotonic assignment.
Q3.Do I need to return the assignment or just the total?
Just the minimum total count. The per-child assignment is computed internally but only the sum is returned.
Q4.Is there always a valid distribution?
Yes — giving everyone 1 already satisfies the floor, and the passes only ever increase counts, so a valid (and minimal) solution always exists.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize that a both-neighbors constraint decomposes into two independent one-directional passes, and whether you correctly combine them with max instead of overwriting.

Where candidates slip

Trying to solve it in a single pass (you can't satisfy both neighbors at once), or overwriting instead of taking max on the right pass — which breaks the left-neighbor guarantee.

How to stand out

State the decomposition explicitly (left rule, right rule, reconcile with max), prove minimality, and offer the O(1)-space one-pass slope-counting solution as the follow-up.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Two Passes (Left→Right then Right→Left)	`O(n)`	`O(n)`	The answer they want. Lead with the decomposition insight: a both-neighbors rule = a left rule + a right rule, reconciled with max.	Read
2	One Pass, O(1) Space (Slope Counting)Optimal	`O(n)`	`O(1)`	Offer when asked to remove the O(n) array. It tracks ascending/descending run lengths instead of storing per-child candy. Harder to get right — only attempt it if you can explain the peak adjustment.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.Explore the full tree

Decomposing the two-sided constraint

How to read it:One pass per direction, reconciled by max. The two-pass greedy is the standard answer.

Rendering diagram…

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Two Passes (Left→Right then Right→Left)

TimeO(n)SpaceO(n)

The answer they want. Lead with the decomposition insight: a both-neighbors rule = a left rule + a right rule, reconciled with max.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

A child must beat BOTH neighbors when it's rated higher. Can one left-to-right pass ever know about the neighbor to its right? What does that suggest about how many passes you need?

2Hint 2Explore hint

Pass 1 (left→right): give everyone 1, then whenever ratings[i] > ratings[i-1], set candy[i] = candy[i-1] + 1. This satisfies every left-neighbor constraint.

3Hint 3Explore hint

Pass 2 (right→left): whenever ratings[i] > ratings[i+1], set candy[i] = max(candy[i], candy[i+1] + 1). The max preserves pass 1's work while adding the right-neighbor guarantee.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

ratings = [1,0,2]

Array state

init

all 1

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final resultsum([2,1,2]) = 5

C · Code with teaching comments

Reference implementation previewpublic int candy(int[] ratings) { int n = ratings.length; int[] candy = new int[n]; Arrays.fill(candy, 1); for (int i = 1; i < n; i++) {Explore the full code

solution.javaJava

Two Passes (Left→Right then Right→Left) — reference

4 teaching notes

1
public int candy(int[] ratings) {
2
    int n = ratings.length;
3
    int[] candy = new int[n];
4
    // Everyone starts at the floor of 1 candy.
5
    Arrays.fill(candy, 1);
6
    for (int i = 1; i < n; i++) {
7
        if (ratings[i] > ratings[i - 1]) {
8
            candy[i] = candy[i - 1] + 1;
9
        }
10
    }
11
    for (int i = n - 2; i >= 0; i--) {
12
        if (ratings[i] > ratings[i + 1]) {
13
            // Right pass: raise only if the right-neighbor demand exceeds pass 1's
14
            // value.
15
            candy[i] = Math.max(candy[i], candy[i + 1] + 1);
16
        }
17
    }
18
    int total = 0;
19
    // Sum the minimal per-child counts.
20
    for (int c : candy) total += c;
21
    return total;
22
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.22 lines

D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(n) space — Two linear passes → O(n) time. A candy[] array of size n → O(n) space.

E · Edge cases and pitfalls6ratings = [1] — Single child → candy [1] → total 1.Explore edge cases

Edge cases handled

ratings = [1]Single child → candy [1] → total 1.
ratings = [2,2,2]All equal, no constraint fires → [1,1,1] → total 3.
ratings = [1,2,3,4,5]Strictly increasing → left pass gives [1,2,3,4,5]; right pass no-op → total 15.

Pitfalls

Overwriting instead of max on the right pass — destroys the left-neighbor guarantee at peaks.
Using >= instead of > — equal ratings impose no constraint; >= over-allocates.
Doing only one pass — leaves every right-side descent under-allocated.

03.2

Approach 2 of 2 · Optimal

One Pass, O(1) Space (Slope Counting)

TimeO(n)SpaceO(1)

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

You don't actually need the whole candy array — only the running length of the current ascending run and descending run.

2Hint 2Explore hint

On an increase, extend the up-run and add its new length. On a decrease, extend the down-run and add its length.

3Hint 3Explore hint

The peak between an up-run and a down-run is shared; when the down-run hasn't yet exceeded the up-run's height, you've counted the peak twice and must subtract one.

A · Core idea

Flat. When ratings are equal, all runs reset to 0 and nothing is added beyond the already-counted floor — matching the 'no constraint between equals' rule.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

ratings = [1,2,3,1,0]

Interactive diagram

Decomposing the two-sided constraint

i=1 (2>1)

Active call / nodeSupporting contextReturned stateNot active

One pass per direction, reconciled by max. The two-pass greedy is the standard answer.

Final result9 (candy would be [1,2,3,2,1])

C · Code with teaching comments

solution.javaJava

One Pass, O(1) Space (Slope Counting) — optimal

4 teaching notes

1
public int candy(int[] ratings) {
2
    int n = ratings.length;
3
    if (n <= 1) return n;
4
    // Pre-pay the floor of one candy per child; additions below are the extras.
5
    int total = n;
6
    int up = 0, down = 0, peak = 0;
7
    for (int i = 1; i < n; i++) {
8
        if (ratings[i] > ratings[i - 1]) {
9
            up++;
10
            down = 0;
11
            peak = up;
12
            total += up;
13
        } else if (ratings[i] == ratings[i - 1]) {
14
            up = 0;
15
            down = 0;
16
            peak = 0;
17
        } else {
18
            up = 0;
19
            down++;
20
            total += down;
21
            if (peak >= down) {
22
                total--;
23
            }
24
        }
25
    }
26
    return total;
27
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.27 lines

D · Why it works and complexityO(n) timeO(1) spaceOpen the invariant and proofExplore the proof

ComplexityO(n) time, O(1) space — A single left-to-right pass with a handful of integer counters → O(n) time, O(1) extra space (no candy array).

E · Edge cases and pitfalls6ratings = [5,4,3,2,1] — All descending, peak stays 0 so no subtraction → total 5+1+2+3+4 = 15.Explore edge cases

Edge cases handled

ratings = [5,4,3,2,1]All descending, peak stays 0 so no subtraction → total 5+1+2+3+4 = 15.
ratings = [1,2,2]i=1 up=1 total→4; i=2 equal resets → total 4.
ratings = [2]n ≤ 1 short-circuit → 1.

Pitfalls

Forgetting to reset down (and peak) when a new ascent starts — leaks stale run lengths.
Subtracting unconditionally on every descent instead of only while peak >= down — under-counts long descents.
Not resetting runs on equal ratings — treats a flat as part of a slope.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int candy(int[] ratings) { int n = ratings.length; if (n <= 1) return n; int total = n; int up = 0, down = 0, peak = 0;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Overwriting instead of taking max on the right pass

At a peak that beats both neighbors, the left pass already set a large value. A plain assignment on the right pass discards it, so the peak may end up ≤ its left neighbor — invalid.

Explore the code comparison

Don't write this

for (int i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
        candy[i] = candy[i + 1] + 1;
    }
}

Write this instead

for (int i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
        candy[i] = Math.max(candy[i], candy[i + 1] + 1);
    }
}

Using >= and over-allocating on equal ratings

Equal-rated neighbors have NO ordering constraint. Using >= forces a strict increase that isn't required, inflating the total (e.g. [1,2,2] would wrongly cost 5 instead of 4).

Explore the code comparison

Don't write this

if ratings[i] >= ratings[i - 1]:
    candy[i] = candy[i - 1] + 1

Write this instead

if ratings[i] > ratings[i - 1]:
    candy[i] = candy[i - 1] + 1

Solving it in one greedy pass

Explore the code comparison

Don't write this

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

Write this instead

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two greedy sweeps (left→right, right→left, take max)

Code pattern to memorize

candy = [1]*n
for i in 1..n-1:
    if r[i] > r[i-1]: candy[i] = candy[i-1] + 1
for i in n-2..0:
    if r[i] > r[i+1]: candy[i] = max(candy[i], candy[i+1] + 1)
return sum(candy)

Rules to remember

1Start everyone at 1 — that satisfies the 'at least one candy' floor.
2Left pass fixes the left-neighbor constraint; right pass fixes the right-neighbor constraint.
3On the right pass, take the max — never overwrite the left pass's result, or you break one side.
4Equal ratings impose no constraint — neighbors with the same rating may differ freely in candy.
5One constraint per direction means one pass per direction; a single pass can't see both neighbors at once.

Use this pattern when

Assign values under local neighbor constraints in both directions
Minimize a total subject to 'strictly greater than smaller neighbor'
Any 1-D problem where each element depends on left AND right context
Slope/peak-valley reasoning over a sequence

Choose another pattern when

Constraint is only one-directional → a single pass suffices
Constraint is non-local (depends on all elements) → not a sweep; think DP or sorting
You need the assignment to be unique → this yields the minimum, not the only valid one
Ratings form a 2-D grid → BFS/DP by value order, not a linear sweep

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Trapping Rain Water
Same two-directional decomposition: each bar's water depends on the max height to its left AND right.
Product of Array Except Self
Prefix pass times suffix pass — combine two directional sweeps into a per-element answer.
Container With Most Water
Two-pointer greedy where each move is justified by which side limits the area.
Partition Labels
Coming soon
Greedy sweep using a precomputed 'last occurrence' to extend partitions — single-direction cousin.

Same pattern

←

Best Time to Buy and Sell Stock II

Continue · Next problem

H-Index