Loading…

hardDynamic ProgrammingFrequently asked

Candies

Q: How do you solve Candies using the Brute Force — Repeated Relaxation approach?

When to use it: State it to show you can reach correctness mechanically, then replace it with the two-pass once you see the cost. The most direct way to *guarantee* a valid distribution: initialise every child to 1 candy, then relax. A relaxation sweep walks the line and, for each child, checks both neighbours: if a child has a strictly higher rating than a neighbour but not strictly more candies, bump it. Repeat sweeps until an entire pass changes nothing. **Why it converges.** Candy counts only ever increase and the minimum valid assignment is bounded, so the process must stabilise. When a sweep makes zero changes, every local rule is satisfied simultaneously — that's exactly the definition of a valid distribution. **Why it's not minimal-effort.** Consider a strictly decreasing run `[5, 4, 3, 2, 1]`. The rightmost child is the smallest and needs 1; its left neighbour needs 2, the next 3, and so on — but each sweep can only push the correction one step leftward, because a child can't know its right neighbour's final value until that value settles. So you need ~`n` sweeps, each `O(n)`, giving `O(n²)`. For `n = 10⁵` that's 10¹⁰ operations — far too slow. **The lesson it teaches.** The reason relaxation is slow is that information from the right propagates left one step at a time. If we instead made *one* dedicated right-to-left pass, that information would travel the whole way in a single sweep. Symmetrically for the left. That observation is precisely the two-pass optimisation. Time complexity: O(n²). Space complexity: O(n).

Q: How do you solve Candies using the Two-Pass Prefix/Suffix DP (Optimal) approach?

When to use it: The answer they want. Phrase it as 'one sweep per direction, merged with max'. Break the two-sided constraint into two one-sided constraints, solve each with a single sweep, and reconcile. **Pass 1 — left to right.** Start every child at 1. Walking rightward, whenever `rating[i] > rating[i-1]`, the child must beat its *left* neighbour: set `candy[i] = candy[i-1] + 1`. After this pass, every ascending run is correctly increasing, but descending runs are still flat at the wrong values because we never looked rightward. **Pass 2 — right to left.** Walking leftward, whenever `rating[i] > rating[i+1]`, the child must beat its *right* neighbour. The candidate value is `candy[i+1] + 1`. But the left pass may already have assigned `candy[i]` a larger value (e.g. at a peak that also dominates its left side). To honour *both* obligations we take the larger: `candy[i] = max(candy[i], candy[i+1] + 1)`. **Why the max is the crux.** A peak that is higher than *both* neighbours must exceed both candy counts. The left pass gives it `leftRun + 1`; the right pass would give it `rightRun + 1`. The correct value is the maximum of the two, and assignment (instead of max) in pass 2 would silently discard the left pass's work, breaking ascending runs that feed into the peak. **Why two passes suffice and are minimal.** After pass 1, the constraint 'greater than smaller left neighbour' holds everywhere. Pass 2's max can only *increase* values, so it never breaks pass 1's guarantees, and it establishes 'greater than smaller right neighbour'. Both rules now hold, and because every increase was forced (each `+1` was the minimum legal bump), the total is minimal. Time complexity: O(n). Space complexity: O(n).

Q: How do you solve Candies using the Slope Counting — O(1) Extra Space approach?

When to use it: Mention as the space-optimal flourish: count ascending/descending run lengths in a single pass. Instead of storing a candy array, accumulate the total directly by tracking slope lengths. Maintain `up` (length of the current ascending run), `down` (length of the current descending run), and `peak` (candies the last peak received). **On an ascent** (`rating[i] > rating[i-1]`): the run grows, `up++`, reset `down = 0`, the current child gets `up + 1` candies, and remember `peak = up + 1`. **On a descent** (`rating[i] < rating[i-1]`): `down++`, reset `up = 0`, and add `down` candies for this child. Crucially, when `down` reaches `peak` the descending side has grown as long as the peak's height, so the peak must itself be raised by one — add an extra `+1` to cover that overlap. **On equal ratings**: both runs reset to 0, the child gets exactly 1. **Why it's correct.** This reproduces the two-pass result by reasoning about each maximal monotone segment: an up-run of length `k` contributes `1+2+…+(k+1)` style growth, a down-run likewise, and the shared peak is counted once at `max(upLen, downLen)+1`. The peak-overlap correction is the algebraic equivalent of the `max` in the two-pass method. **Why ship it.** Same `O(n)` time but no auxiliary array — useful when memory is tight. It's trickier to get right (the peak correction is subtle), so reach for the clean two-pass unless O(1) space is explicitly demanded. Time complexity: O(n). Space complexity: O(1).

Dynamic Programming · 32 of 44 · 11 min

Alice is a teacher with n students standing in a line, each with a rating. She wants to give candies subject to two rules:

1
Every student must receive at least one candy.
2
Any student with a strictly higher rating than an immediate neighbour must receive strictly more candies than that neighbour.

Given the array of ratings, return the minimum total number of candies Alice must distribute.

In plain English

Each child has two local obligations: out-rank the left neighbour and out-rank the right neighbour in candies — but only against whichever of them has a strictly lower rating. A naive 'give one more than the bigger neighbour' is circular because that neighbour's count isn't fixed yet. Splitting the obligation into a left-facing pass and a right-facing pass breaks the circularity, and a final max reconciles peaks that must dominate both sides.

Examples

Example 1

Input: ratings = [1, 2, 2]
Output: 4
Note: Candies [1, 2, 1]. Child 1 out-ranks child 0 (2 > 1) → 2 candies. Child 2 has equal rating to child 1, so it may stay at 1. Total 1+2+1 = 4.

Example 2

Input: ratings = [1, 2, 2, 3, 1]
Output: 7
Note: Candies [1, 2, 1, 2, 1]. Each ascending step bumps by one; the equal pair (2,2) and the final drop (3>1) cost only the minimum. Total 7.

Example 3

Input: ratings = [2, 4, 2, 6, 1, 7, 8, 9, 2, 1]
Output: 19
Note: Candies [1, 2, 1, 2, 1, 2, 3, 4, 2, 1] — peaks at indices 1, 3, 7 take more, valleys reset to 1. Total 19.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ rating[i] ≤ 10⁹
Only strictly-greater ratings impose a constraint; equal-rated neighbours are unconstrained relative to each other
Every child receives at least one candy

Clarifying questions4First question: If two adjacent children have equal ratings, must their candy counts differ?Explore questions

Q1.If two adjacent children have equal ratings, must their candy counts differ?
No. The rule fires only on *strictly* higher ratings, so equal-rated neighbours can both hold the minimum. This is the most common misread.
Q2.Is the line circular (does the last child neighbour the first)?
No, it's a straight line. A circular version would need relaxation until stable rather than a clean two-pass.
Q3.Do we need the actual distribution or just the total?
Just the minimum total here. The two-pass naturally builds a valid per-child assignment, so you can return either.
Q4.Can ratings be large or repeated?
Yes, up to 10⁹ and repeated freely. Only relative order between adjacent ratings matters, so magnitude is irrelevant.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Children stand in a line, each with a rating; every child gets at least one candy, and any child with a strictly higher rating than an immediate neighbour must get more candies than that neighbour. Minimize the total. The trick is two sweeps: left-to-right enforce the 'higher than left neighbour' rule (candy[i] = candy[i-1] + 1 when rating[i] > rating[i-1]), then right-to-left enforce the 'higher than right neighbour' rule with a max so you don't break the first pass (candy[i] = max(candy[i], candy[i+1] + 1) when rating[i] > rating[i+1]). Sum the array. O(n) time, O(n) space.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognise that a single greedy sweep can't satisfy constraints coming from both neighbours, and that two directional passes combined with max resolve them in linear time.

Where candidates slip

Doing only a left-to-right pass (ignores descending runs), or overwriting with assignment in the second pass instead of taking the max — both undercount.

How to stand out

Explain why one pass fails with a concrete descending example, then derive the two-pass max merge and note the O(1)-space slope-counting alternative.

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	Brute Force — Repeated Relaxation	`O(n²)`	`O(n)`	State it to show you can reach correctness mechanically, then replace it with the two-pass once you see the cost.	Read
2	Two-Pass Prefix/Suffix DP (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'one sweep per direction, merged with max'.	Read
3	Slope Counting — O(1) Extra Space	`O(n)`	`O(1)`	Mention as the space-optimal flourish: count ascending/descending run lengths in a single pass.	Read

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

Why two passes are needed

How to read it:Each child's count is the max of what its left run and right run demand.

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 3

Brute Force — Repeated Relaxation

TimeO(n²)SpaceO(n)

State it to show you can reach correctness mechanically, then replace it with the two-pass once you see the cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Start everyone at 1 candy. Now repeatedly scan the line: wherever a child violates a neighbour rule, bump that child up by one.

2Hint 2Explore hint

Keep sweeping until a full pass makes no changes — at that point every constraint holds.

3Hint 3Explore hint

How many sweeps could you need in the worst case? A long descending run like [5,4,3,2,1] propagates one fix per sweep, giving O(n) sweeps × O(n) work.

A · Core idea

The most direct way to guarantee a valid distribution: initialise every child to 1 candy, then relax. A relaxation sweep walks the line and, for each child, checks both neighbours: if a child has a strictly higher rating than a neighbour but not strictly more candies, bump it. Repeat sweeps until an entire pass changes nothing.

Why it converges. Candy counts only ever increase and the minimum valid assignment is bounded, so the process must stabilise. When a sweep makes zero changes, every local rule is satisfied simultaneously — that's exactly the definition of a valid distribution.

Why it's not minimal-effort. Consider a strictly decreasing run [5, 4, 3, 2, 1]. The rightmost child is the smallest and needs 1; its left neighbour needs 2, the next 3, and so on — but each sweep can only push the correction one step leftward, because a child can't know its right neighbour's final value until that value settles. So you need ~`nsweeps, eachO(n), giving O(n²). For n = 10⁵` that's 10¹⁰ operations — far too slow.

The lesson it teaches. The reason relaxation is slow is that information from the right propagates left one step at a time. If we instead made one dedicated right-to-left pass, that information would travel the whole way in a single sweep. Symmetrically for the left. That observation is precisely the two-pass optimisation.

B · Visual dry run

Interactive dry run

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

ratings = [3, 2, 1]

Array state

init

all 1

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

Reference implementation previewpublic long candies(int n, List<Integer> ratings) { int[] r = ratings.stream().mapToInt(Integer::intValue).toArray(); int[] candy = new int[n]; java.util.Arrays.fill(candy, 1); boolean changed = true;Explore the full code

solution.javaJava

Brute Force — Repeated Relaxation — reference

4 teaching notes

1
public long candies(int n, List<Integer> ratings) {
2
    int[] r = ratings.stream().mapToInt(Integer::intValue).toArray();
3
    int[] candy = new int[n];
4
    // Every child starts at the guaranteed floor of 1 candy.
5
    java.util.Arrays.fill(candy, 1);
6
    boolean changed = true;
7
    // Keep sweeping until a full pass changes nothing — the convergence condition.
8
    while (changed) {
9
        changed = false;
10
        for (int i = 0; i < n; i++) {
11
            // Left-neighbour violation: higher rating but not strictly more candies.
12
            if (i > 0 && r[i] > r[i - 1] && candy[i] <= candy[i - 1]) {
13
                candy[i] = candy[i - 1] + 1;
14
                changed = true;
15
            }
16
            if (i < n - 1 && r[i] > r[i + 1] && candy[i] <= candy[i + 1]) {
17
                // Right-neighbour fix — but this only propagates one step per sweep.
18
                candy[i] = candy[i + 1] + 1;
19
                changed = true;
20
            }
21
        }
22
    }
23
    long total = 0;
24
    for (int c : candy) total += c;
25
    return total;
26
}

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

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

Repeated relaxation is slow because constraint information crawls one index per sweep. Giving each direction its own single dedicated sweep lets the information travel the full length at once — turning O(n²) into O(n).

ComplexityO(n²) time, O(n) space — Each sweep is O(n). A monotone run forces the correction to ripple one position per sweep, so up to O(n) sweeps → O(n²) worst case.

E · Edge cases and pitfalls3Forgetting the changed flag → either infinite loop or stopping before stable.Explore edge cases

Pitfalls

Forgetting the changed flag → either infinite loop or stopping before stable.
Using <= vs < incorrectly — must be strictly more candies for a strictly higher rating.
Running it at n = 10⁵ on a long monotone run — O(n²) is far too slow.

03.2

Approach 2 of 3 · Optimal

Two-Pass Prefix/Suffix DP (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'one sweep per direction, merged with max'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Split the obligation in two. First handle only the left neighbour: scan left→right and set candy[i] = candy[i-1] + 1 whenever rating[i] > rating[i-1].

2Hint 2Explore hint

Now handle only the right neighbour: scan right→left and require candy[i] > candy[i+1] when rating[i] > rating[i+1].

3Hint 3Explore hint

The second pass must not undo the first — combine with max: candy[i] = max(candy[i], candy[i+1] + 1).

A · Core idea

Break the two-sided constraint into two one-sided constraints, solve each with a single sweep, and reconcile.

Pass 1 — left to right. Start every child at 1. Walking rightward, whenever rating[i] > rating[i-1], the child must beat its left neighbour: set candy[i] = candy[i-1] + 1. After this pass, every ascending run is correctly increasing, but descending runs are still flat at the wrong values because we never looked rightward.

Pass 2 — right to left. Walking leftward, whenever rating[i] > rating[i+1], the child must beat its right neighbour. The candidate value is candy[i+1] + 1. But the left pass may already have assigned candy[i] a larger value (e.g. at a peak that also dominates its left side). To honour both obligations we take the larger: candy[i] = max(candy[i], candy[i+1] + 1).

Why the max is the crux. A peak that is higher than both neighbours must exceed both candy counts. The left pass gives it leftRun + 1; the right pass would give it rightRun + 1. The correct value is the maximum of the two, and assignment (instead of max) in pass 2 would silently discard the left pass's work, breaking ascending runs that feed into the peak.

Why two passes suffice and are minimal. After pass 1, the constraint 'greater than smaller left neighbour' holds everywhere. Pass 2's max can only increase values, so it never breaks pass 1's guarantees, and it establishes 'greater than smaller right neighbour'. Both rules now hold, and because every increase was forced (each +1 was the minimum legal bump), the total is minimal.

B · Visual dry run

Interactive dry run

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

ratings = [2, 4, 2, 6, 1, 7, 8, 9, 2, 1]

Array state

pass 1

2>1 → 2; 2==2 stays 1; 3>2 → 2; 1<3 stays 1

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result19

C · Code with teaching comments

solution.javaJava

Two-Pass Prefix/Suffix DP (Optimal) — optimal

4 teaching notes

1
public long candies(int n, List<Integer> ratings) {
2
    int[] r = ratings.stream().mapToInt(Integer::intValue).toArray();
3
    int[] candy = new int[n];
4
    // Floor of 1 candy each — the minimum before any constraint is applied.
5
    java.util.Arrays.fill(candy, 1);
6
    for (int i = 1; i < n; i++) {
7
        // Left pass: out-rank the left neighbour by exactly one.
8
        if (r[i] > r[i - 1]) candy[i] = candy[i - 1] + 1;
9
    }
10
    for (int i = n - 2; i >= 0; i--) {
11
        // Right pass with max: out-rank the right neighbour without erasing the left
12
        // pass.
13
        if (r[i] > r[i + 1]) candy[i] = Math.max(candy[i], candy[i + 1] + 1);
14
    }
15
    // Use long — n·maxCandy can exceed int range when n is large.
16
    long total = 0;
17
    for (int c : candy) total += c;
18
    return total;
19
}

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

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

A constraint that points in two directions decomposes into two independent one-directional constraints. Solve each in its own linear sweep, then merge with max — the max is what lets a peak satisfy both sides simultaneously without re-running anything.

ComplexityO(n) time, O(n) space — Two linear passes plus a sum, each O(n), with constant work per element → O(n) time. One auxiliary array of size n → O(n) space.

E · Edge cases and pitfalls7ratings = [1, 2, 2] — Pass1 → [1,2,1]; pass2 no change (2 not > right). Sum 4. Equal pair stays minimal.Explore edge cases

Edge cases handled

ratings = [1, 2, 2]Pass1 → [1,2,1]; pass2 no change (2 not > right). Sum 4. Equal pair stays minimal.
ratings = [5, 4, 3, 2, 1]Pass1 all 1 (strictly descending); pass2 → [5,4,3,2,1]. Sum 15. Single right pass fixes the whole descent.
ratings = [1]No neighbours; candy = [1]; sum 1.
ratings = [1, 3, 2, 2, 1]Pass1 → [1,2,1,1,1]; pass2 → [1,2,1,2,1] (index2: 2>1 but right is 2 not less; index3: 2>1 → 2). Sum 7.

Pitfalls

Using assignment instead of max in the second pass — wipes out the left pass at peaks.
Using >= instead of > — over-allocates on equal ratings.
Summing into an int — overflow at n = 10⁵; accumulate in long.

03.3

Approach 3 of 3

Slope Counting — O(1) Extra Space

TimeO(n)SpaceO(1)

Mention as the space-optimal flourish: count ascending/descending run lengths in a single pass.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk once, tracking the length of the current strictly-increasing run (up) and strictly-decreasing run (down).

2Hint 2Explore hint

On a rise, the child gets up+1 candies; on a fall, grow the down run and add it; equal ratings reset both runs to 0 and give 1.

3Hint 3Explore hint

A peak is shared between the up and down slopes — subtract one overlap when the down run grows past the up run so the peak isn't double-counted.

A · Core idea

Instead of storing a candy array, accumulate the total directly by tracking slope lengths. Maintain up (length of the current ascending run), down (length of the current descending run), and peak (candies the last peak received).

On an ascent (rating[i] > rating[i-1]): the run grows, up++, reset down = 0, the current child gets up + 1 candies, and remember peak = up + 1.

On a descent (rating[i] < rating[i-1]): down++, reset up = 0, and add down candies for this child. Crucially, when down reaches peak the descending side has grown as long as the peak's height, so the peak must itself be raised by one — add an extra +1 to cover that overlap.

On equal ratings: both runs reset to 0, the child gets exactly 1.

Why it's correct. This reproduces the two-pass result by reasoning about each maximal monotone segment: an up-run of length k contributes 1+2+…+(k+1) style growth, a down-run likewise, and the shared peak is counted once at max(upLen, downLen)+1. The peak-overlap correction is the algebraic equivalent of the max in the two-pass method.

Why ship it. Same O(n) time but no auxiliary array — useful when memory is tight. It's trickier to get right (the peak correction is subtle), so reach for the clean two-pass unless O(1) space is explicitly demanded.

B · Visual dry run

Interactive dry run

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

ratings = [1, 3, 2, 1]

Array state

ascend

up=1, peak=2

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

Reference implementation previewpublic long candies(int n, List<Integer> ratings) { int[] r = ratings.stream().mapToInt(Integer::intValue).toArray(); if (n == 0) return 0; long total = 1; int up = 0, down = 0, peak = 1;Explore the full code

solution.javaJava

Slope Counting — O(1) Extra Space — reference

4 teaching notes

1
public long candies(int n, List<Integer> ratings) {
2
    int[] r = ratings.stream().mapToInt(Integer::intValue).toArray();
3
    if (n == 0) return 0;
4
    // First child always gets 1; the loop handles the rest relative to it.
5
    long total = 1;
6
    int up = 0, down = 0, peak = 1;
7
    for (int i = 1; i < n; i++) {
8
        if (r[i] > r[i - 1]) {
9
            // Ascending run grows; this child's candy and the new peak height are up+1.
10
            up++; down = 0; peak = up + 1;
11
            total += peak;
12
        } else if (r[i] < r[i - 1]) {
13
            up = 0; down++;
14
            // Descent adds down candies; once the descent matches the peak, lift the
15
            // peak by one.
16
            total += down + (down >= peak ? 1 : 0);
17
        } else {
18
            // Equal ratings break both runs — this child resets to 1.
19
            up = 0; down = 0; peak = 1;
20
            total += 1;
21
        }
22
    }
23
    return total;
24
}

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

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

The two-pass max is really comparing the length of the ascending run to the descending run at each peak. Counting those run lengths directly lets you skip the array entirely — the peak gets max(up, down)+1, and everything else telescopes into the running sum.

ComplexityO(n) time, O(1) space — A single pass with constant bookkeeping per element → O(n) time and O(1) extra space (no candy array materialised).

E · Edge cases and pitfalls6ratings = [1, 2, 2] — i=1 ascend (up=1, +2); i=2 equal (reset, +1). total = 1+2+1 = 4.Explore edge cases

Edge cases handled

ratings = [1, 2, 2]i=1 ascend (up=1, +2); i=2 equal (reset, +1). total = 1+2+1 = 4.
ratings = [5, 4, 3, 2, 1]Pure descent: adds 1+2+3+4 with peak corrections folding in → total 15.
ratings = [1]Loop skipped; total stays 1.

Pitfalls

Forgetting the peak-overlap correction → undercounts long descents after a peak.
Not resetting both up and down on equal ratings → carries a stale slope.
Treating equal ratings as ascending or descending → over-allocates.

Practice

Try the solution yourself

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

Editable code previewpublic long candies(int n, List<Integer> ratings) { int[] r = ratings.stream().mapToInt(Integer::intValue).toArray(); int[] candy = new int[n]; java.util.Arrays.fill(candy, 1); for (int i = 1; i < n; i++) {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.

Single-pass greedy

A left-only pass leaves descending runs flat. On [5,4,3,2,1] it returns all 1s (sum 5) instead of [5,4,3,2,1] (sum 15).

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)  # ignores right neighbours

Write this instead

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

Assignment instead of max in pass 2

At a peak the left pass earned a large value; plain assignment in pass 2 overwrites it with the smaller right-based value, breaking the ascending run feeding the peak.

Explore the code comparison

Don't write this

if (r[i] > r[i + 1]) candy[i] = candy[i + 1] + 1;  // erases left pass

Write this instead

if (r[i] > r[i + 1]) candy[i] = Math.max(candy[i], candy[i + 1] + 1);

Using >= on equal ratings

Equal ratings impose no constraint. Bumping on >= over-allocates: [2,2] would cost 3 instead of the correct 2.

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-pass prefix/suffix DP (left constraint then right constraint, combined with max)

Code pattern to memorize

candy = [1]*n
# left → right: satisfy left neighbour
for i in 1..n-1:
    if rating[i] > rating[i-1]: candy[i] = candy[i-1] + 1
# right → left: satisfy right neighbour without breaking left
for i in n-2..0:
    if rating[i] > rating[i+1]: candy[i] = max(candy[i], candy[i+1] + 1)
return sum(candy)

Rules to remember

1Each child starts at 1 candy — that's the floor every child is guaranteed.
2Only a strictly higher rating forces more candy. Equal ratings impose no constraint, so neighbours with equal ratings can both stay at 1.
3The second pass uses max, not assignment: candy[i] = max(candy[i], candy[i+1]+1). Plain assignment would erase what the left pass earned.
4One pass alone is always wrong — left-only ignores right neighbours and vice versa. You need both directions reconciled.
5A child sitting at a local peak takes max(left_run, right_run) + 1; the two passes deliver exactly that without you computing runs explicitly.

Use this pattern when

A linear arrangement where each element must beat its neighbour under a local comparison
Constraints point in both directions (left neighbour AND right neighbour) and must be merged
Minimize/assign values subject to 'strictly greater than smaller neighbour' rules
Ratings, heights, or priorities on a line with relative ordering requirements

Choose another pattern when

Comparisons are global (sort-based), not between adjacent elements → sorting / heap, not two sweeps
It's a 2D grid of constraints, not a line → grid DP / BFS relaxation
Equal elements must also differ → the strict-vs-equal rule changes; re-derive
You need the assignment for a cycle (last neighbours first) → relaxation loop, not a clean two-pass

Interview takeaway

When local constraints push from both sides, satisfy each direction in its own sweep and merge with max. Two linear passes beat any single greedy guess and any repeated-relaxation loop — this left-then-right-with-max template solves Candies, Trapping Rain Water's volume idea, 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-pass prefix/suffix DP: when a constraint points both left and right, satisfy each direction in its own linear sweep and merge with max (or min). Same skeleton as Candy, Product of Array Except Self, and Trapping Rain Water — recognise bidirectional local constraints and reach for two sweeps over any relaxation loop.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Candy
Coming soon
The identical problem on LeetCode — same two-pass max template.
Product of Array Except Self
Coming soon
Same prefix-then-suffix two-pass idea, combining left and right contributions.
Trapping Rain Water
Coming soon
Left-max and right-max prefix/suffix arrays, merged with min — the dual of this pattern.
Maximum Subarray
Coming soon
Single-pass running DP — contrast for when one direction suffices.

Same pattern

←

Abbreviation

Continue · Next problem

Construct the Array

hardDynamic ProgrammingFrequently asked

Candies

Dynamic Programming · 32 of 44 · 11 min

Alice is a teacher with n students standing in a line, each with a rating. She wants to give candies subject to two rules:

1
Every student must receive at least one candy.
2
Any student with a strictly higher rating than an immediate neighbour must receive strictly more candies than that neighbour.

Given the array of ratings, return the minimum total number of candies Alice must distribute.

In plain English

Examples

Example 1

Input: ratings = [1, 2, 2]
Output: 4
Note: Candies [1, 2, 1]. Child 1 out-ranks child 0 (2 > 1) → 2 candies. Child 2 has equal rating to child 1, so it may stay at 1. Total 1+2+1 = 4.

Example 2

Input: ratings = [1, 2, 2, 3, 1]
Output: 7
Note: Candies [1, 2, 1, 2, 1]. Each ascending step bumps by one; the equal pair (2,2) and the final drop (3>1) cost only the minimum. Total 7.

Example 3

Input: ratings = [2, 4, 2, 6, 1, 7, 8, 9, 2, 1]
Output: 19
Note: Candies [1, 2, 1, 2, 1, 2, 3, 4, 2, 1] — peaks at indices 1, 3, 7 take more, valleys reset to 1. Total 19.

Constraints

1 ≤ n ≤ 10⁵
1 ≤ rating[i] ≤ 10⁹
Only strictly-greater ratings impose a constraint; equal-rated neighbours are unconstrained relative to each other
Every child receives at least one candy

Clarifying questions4First question: If two adjacent children have equal ratings, must their candy counts differ?Explore questions

Q1.If two adjacent children have equal ratings, must their candy counts differ?
No. The rule fires only on *strictly* higher ratings, so equal-rated neighbours can both hold the minimum. This is the most common misread.
Q2.Is the line circular (does the last child neighbour the first)?
No, it's a straight line. A circular version would need relaxation until stable rather than a clean two-pass.
Q3.Do we need the actual distribution or just the total?
Just the minimum total here. The two-pass naturally builds a valid per-child assignment, so you can return either.
Q4.Can ratings be large or repeated?
Yes, up to 10⁹ and repeated freely. Only relative order between adjacent ratings matters, so magnitude is irrelevant.

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 recognise that a single greedy sweep can't satisfy constraints coming from both neighbours, and that two directional passes combined with max resolve them in linear time.

Where candidates slip

Doing only a left-to-right pass (ignores descending runs), or overwriting with assignment in the second pass instead of taking the max — both undercount.

How to stand out

Explain why one pass fails with a concrete descending example, then derive the two-pass max merge and note the O(1)-space slope-counting alternative.

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	Brute Force — Repeated Relaxation	`O(n²)`	`O(n)`	State it to show you can reach correctness mechanically, then replace it with the two-pass once you see the cost.	Read
2	Two-Pass Prefix/Suffix DP (Optimal)Optimal	`O(n)`	`O(n)`	The answer they want. Phrase it as 'one sweep per direction, merged with max'.	Read
3	Slope Counting — O(1) Extra Space	`O(n)`	`O(1)`	Mention as the space-optimal flourish: count ascending/descending run lengths in a single pass.	Read

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

Why two passes are needed

How to read it:Each child's count is the max of what its left run and right run demand.

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 3

Brute Force — Repeated Relaxation

TimeO(n²)SpaceO(n)

State it to show you can reach correctness mechanically, then replace it with the two-pass once you see the cost.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Start everyone at 1 candy. Now repeatedly scan the line: wherever a child violates a neighbour rule, bump that child up by one.

2Hint 2Explore hint

Keep sweeping until a full pass makes no changes — at that point every constraint holds.

3Hint 3Explore hint

How many sweeps could you need in the worst case? A long descending run like [5,4,3,2,1] propagates one fix per sweep, giving O(n) sweeps × O(n) work.

A · Core idea

B · Visual dry run

Interactive dry run

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

ratings = [3, 2, 1]

Array state

init

all 1

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final result6

C · Code with teaching comments

solution.javaJava

Brute Force — Repeated Relaxation — reference

4 teaching notes

1
public long candies(int n, List<Integer> ratings) {
2
    int[] r = ratings.stream().mapToInt(Integer::intValue).toArray();
3
    int[] candy = new int[n];
4
    // Every child starts at the guaranteed floor of 1 candy.
5
    java.util.Arrays.fill(candy, 1);
6
    boolean changed = true;
7
    // Keep sweeping until a full pass changes nothing — the convergence condition.
8
    while (changed) {
9
        changed = false;
10
        for (int i = 0; i < n; i++) {
11
            // Left-neighbour violation: higher rating but not strictly more candies.
12
            if (i > 0 && r[i] > r[i - 1] && candy[i] <= candy[i - 1]) {
13
                candy[i] = candy[i - 1] + 1;
14
                changed = true;
15
            }
16
            if (i < n - 1 && r[i] > r[i + 1] && candy[i] <= candy[i + 1]) {
17
                // Right-neighbour fix — but this only propagates one step per sweep.
18
                candy[i] = candy[i + 1] + 1;
19
                changed = true;
20
            }
21
        }
22
    }
23
    long total = 0;
24
    for (int c : candy) total += c;
25
    return total;
26
}

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

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

ComplexityO(n²) time, O(n) space — Each sweep is O(n). A monotone run forces the correction to ripple one position per sweep, so up to O(n) sweeps → O(n²) worst case.

E · Edge cases and pitfalls3Forgetting the changed flag → either infinite loop or stopping before stable.Explore edge cases

Pitfalls

Forgetting the changed flag → either infinite loop or stopping before stable.
Using <= vs < incorrectly — must be strictly more candies for a strictly higher rating.
Running it at n = 10⁵ on a long monotone run — O(n²) is far too slow.

03.2

Approach 2 of 3 · Optimal

Two-Pass Prefix/Suffix DP (Optimal)

TimeO(n)SpaceO(n)

The answer they want. Phrase it as 'one sweep per direction, merged with max'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Split the obligation in two. First handle only the left neighbour: scan left→right and set candy[i] = candy[i-1] + 1 whenever rating[i] > rating[i-1].

2Hint 2Explore hint

Now handle only the right neighbour: scan right→left and require candy[i] > candy[i+1] when rating[i] > rating[i+1].

3Hint 3Explore hint

The second pass must not undo the first — combine with max: candy[i] = max(candy[i], candy[i+1] + 1).

A · Core idea

Break the two-sided constraint into two one-sided constraints, solve each with a single sweep, and reconcile.

B · Visual dry run

Interactive dry run

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

ratings = [2, 4, 2, 6, 1, 7, 8, 9, 2, 1]

Array state

pass 1

2>1 → 2; 2==2 stays 1; 3>2 → 2; 1<3 stays 1

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result19

C · Code with teaching comments

solution.javaJava

Two-Pass Prefix/Suffix DP (Optimal) — optimal

4 teaching notes

1
public long candies(int n, List<Integer> ratings) {
2
    int[] r = ratings.stream().mapToInt(Integer::intValue).toArray();
3
    int[] candy = new int[n];
4
    // Floor of 1 candy each — the minimum before any constraint is applied.
5
    java.util.Arrays.fill(candy, 1);
6
    for (int i = 1; i < n; i++) {
7
        // Left pass: out-rank the left neighbour by exactly one.
8
        if (r[i] > r[i - 1]) candy[i] = candy[i - 1] + 1;
9
    }
10
    for (int i = n - 2; i >= 0; i--) {
11
        // Right pass with max: out-rank the right neighbour without erasing the left
12
        // pass.
13
        if (r[i] > r[i + 1]) candy[i] = Math.max(candy[i], candy[i + 1] + 1);
14
    }
15
    // Use long — n·maxCandy can exceed int range when n is large.
16
    long total = 0;
17
    for (int c : candy) total += c;
18
    return total;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 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 plus a sum, each O(n), with constant work per element → O(n) time. One auxiliary array of size n → O(n) space.

E · Edge cases and pitfalls7ratings = [1, 2, 2] — Pass1 → [1,2,1]; pass2 no change (2 not > right). Sum 4. Equal pair stays minimal.Explore edge cases

Edge cases handled

ratings = [1, 2, 2]Pass1 → [1,2,1]; pass2 no change (2 not > right). Sum 4. Equal pair stays minimal.
ratings = [5, 4, 3, 2, 1]Pass1 all 1 (strictly descending); pass2 → [5,4,3,2,1]. Sum 15. Single right pass fixes the whole descent.
ratings = [1]No neighbours; candy = [1]; sum 1.
ratings = [1, 3, 2, 2, 1]Pass1 → [1,2,1,1,1]; pass2 → [1,2,1,2,1] (index2: 2>1 but right is 2 not less; index3: 2>1 → 2). Sum 7.

Pitfalls

Using assignment instead of max in the second pass — wipes out the left pass at peaks.
Using >= instead of > — over-allocates on equal ratings.
Summing into an int — overflow at n = 10⁵; accumulate in long.

03.3

Approach 3 of 3

Slope Counting — O(1) Extra Space

TimeO(n)SpaceO(1)

Mention as the space-optimal flourish: count ascending/descending run lengths in a single pass.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Walk once, tracking the length of the current strictly-increasing run (up) and strictly-decreasing run (down).

2Hint 2Explore hint

On a rise, the child gets up+1 candies; on a fall, grow the down run and add it; equal ratings reset both runs to 0 and give 1.

3Hint 3Explore hint

A peak is shared between the up and down slopes — subtract one overlap when the down run grows past the up run so the peak isn't double-counted.

A · Core idea

On an ascent (rating[i] > rating[i-1]): the run grows, up++, reset down = 0, the current child gets up + 1 candies, and remember peak = up + 1.

On equal ratings: both runs reset to 0, the child gets exactly 1.

B · Visual dry run

Interactive dry run

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

ratings = [1, 3, 2, 1]

Array state

ascend

up=1, peak=2

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result7

C · Code with teaching comments

solution.javaJava

Slope Counting — O(1) Extra Space — reference

4 teaching notes

1
public long candies(int n, List<Integer> ratings) {
2
    int[] r = ratings.stream().mapToInt(Integer::intValue).toArray();
3
    if (n == 0) return 0;
4
    // First child always gets 1; the loop handles the rest relative to it.
5
    long total = 1;
6
    int up = 0, down = 0, peak = 1;
7
    for (int i = 1; i < n; i++) {
8
        if (r[i] > r[i - 1]) {
9
            // Ascending run grows; this child's candy and the new peak height are up+1.
10
            up++; down = 0; peak = up + 1;
11
            total += peak;
12
        } else if (r[i] < r[i - 1]) {
13
            up = 0; down++;
14
            // Descent adds down candies; once the descent matches the peak, lift the
15
            // peak by one.
16
            total += down + (down >= peak ? 1 : 0);
17
        } else {
18
            // Equal ratings break both runs — this child resets to 1.
19
            up = 0; down = 0; peak = 1;
20
            total += 1;
21
        }
22
    }
23
    return total;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 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 pass with constant bookkeeping per element → O(n) time and O(1) extra space (no candy array materialised).

E · Edge cases and pitfalls6ratings = [1, 2, 2] — i=1 ascend (up=1, +2); i=2 equal (reset, +1). total = 1+2+1 = 4.Explore edge cases

Edge cases handled

ratings = [1, 2, 2]i=1 ascend (up=1, +2); i=2 equal (reset, +1). total = 1+2+1 = 4.
ratings = [5, 4, 3, 2, 1]Pure descent: adds 1+2+3+4 with peak corrections folding in → total 15.
ratings = [1]Loop skipped; total stays 1.

Pitfalls

Forgetting the peak-overlap correction → undercounts long descents after a peak.
Not resetting both up and down on equal ratings → carries a stale slope.
Treating equal ratings as ascending or descending → over-allocates.

Practice

Try the solution yourself

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

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.

Single-pass greedy

A left-only pass leaves descending runs flat. On [5,4,3,2,1] it returns all 1s (sum 5) instead of [5,4,3,2,1] (sum 15).

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)  # ignores right neighbours

Write this instead

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

Assignment instead of max in pass 2

At a peak the left pass earned a large value; plain assignment in pass 2 overwrites it with the smaller right-based value, breaking the ascending run feeding the peak.

Explore the code comparison

Don't write this

if (r[i] > r[i + 1]) candy[i] = candy[i + 1] + 1;  // erases left pass

Write this instead

if (r[i] > r[i + 1]) candy[i] = Math.max(candy[i], candy[i + 1] + 1);

Using >= on equal ratings

Equal ratings impose no constraint. Bumping on >= over-allocates: [2,2] would cost 3 instead of the correct 2.

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

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two-pass prefix/suffix DP (left constraint then right constraint, combined with max)

Code pattern to memorize

candy = [1]*n
# left → right: satisfy left neighbour
for i in 1..n-1:
    if rating[i] > rating[i-1]: candy[i] = candy[i-1] + 1
# right → left: satisfy right neighbour without breaking left
for i in n-2..0:
    if rating[i] > rating[i+1]: candy[i] = max(candy[i], candy[i+1] + 1)
return sum(candy)

Rules to remember

1Each child starts at 1 candy — that's the floor every child is guaranteed.
2Only a strictly higher rating forces more candy. Equal ratings impose no constraint, so neighbours with equal ratings can both stay at 1.
3The second pass uses max, not assignment: candy[i] = max(candy[i], candy[i+1]+1). Plain assignment would erase what the left pass earned.
4One pass alone is always wrong — left-only ignores right neighbours and vice versa. You need both directions reconciled.
5A child sitting at a local peak takes max(left_run, right_run) + 1; the two passes deliver exactly that without you computing runs explicitly.

Use this pattern when

A linear arrangement where each element must beat its neighbour under a local comparison
Constraints point in both directions (left neighbour AND right neighbour) and must be merged
Minimize/assign values subject to 'strictly greater than smaller neighbour' rules
Ratings, heights, or priorities on a line with relative ordering requirements

Choose another pattern when

Comparisons are global (sort-based), not between adjacent elements → sorting / heap, not two sweeps
It's a 2D grid of constraints, not a line → grid DP / BFS relaxation
Equal elements must also differ → the strict-vs-equal rule changes; re-derive
You need the assignment for a cycle (last neighbours first) → relaxation loop, not a clean two-pass

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

Candy
Coming soon
The identical problem on LeetCode — same two-pass max template.
Product of Array Except Self
Coming soon
Same prefix-then-suffix two-pass idea, combining left and right contributions.
Trapping Rain Water
Coming soon
Left-max and right-max prefix/suffix arrays, merged with min — the dual of this pattern.
Maximum Subarray
Coming soon
Single-pass running DP — contrast for when one direction suffices.

Same pattern

←

Abbreviation

Continue · Next problem

Construct the Array