#135 Candy

frequently reported atAmazon Microsoft Google

the problem

In plain words

Children stand in a line, each with a rating. Every child gets at least 1 candy, and a child with a higher rating than a neighbour must get more candies than that neighbour. Return the smallest total number of candies.

in ratings = [1,0,2]

out 5

2, 1, 2.

in ratings = [1,2,2]

out 4

1, 2, 1. Equal ratings have no rule between them.

1 ≤ n ≤ 5·10⁴
0 ≤ ratings[i] ≤ 5·10⁴

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternPrefix & suffix passes Greedy choice

Split the two-sided rule into two one-sided rules. A left-to-right pass fixes "more than the left neighbour", and a right-to-left pass fixes "more than the right". Taking the max satisfies both with the fewest candies.

solutions

From brute force to optimal

Start everyone at 1. Sweep repeatedly, bumping any child who breaks a rule.

candies = all 1.
While something changed, fix each violated neighbour rule.
Sum.

timeO(n²)

Each sweep is O(n), and a long falling run can need up to n sweeps.

spaceO(n)

The candies array.

javajava.util.*

1class Solution {2    public int candy(int[] ratings) {3        int n = ratings.length;4        int[] candies = new int[n];5        Arrays.fill(candies, 1);6        boolean changed = true;7        while (changed) {                                   // keep fixing until every rule holds8            changed = false;9            for (int i = 0; i < n; i++) {10                if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) {11                    candies[i] = candies[i - 1] + 1;12                    changed = true;13                }14                if (i < n - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {15                    candies[i] = candies[i + 1] + 1;16                    changed = true;17                }18            }19        }20        int sum = 0;21        for (int c : candies) sum += c;22        return sum;23    }24}

left[i] handles only the left neighbour, right[i] only the right. Each child gets max(left[i], right[i]).

left: increase when ratings rise left to right.
right: increase when ratings rise right to left.
Sum the max.

timeO(n)

Three passes.

spaceO(n)

Two arrays.

javajava.util.*

1class Solution {2    public int candy(int[] ratings) {3        int n = ratings.length;4        int[] left = new int[n], right = new int[n];5        Arrays.fill(left, 1);6        Arrays.fill(right, 1);7        for (int i = 1; i < n; i++)                         // only the left-neighbour rule8            if (ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;9        for (int i = n - 2; i >= 0; i--)                    // only the right-neighbour rule10            if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;11        int sum = 0;12        for (int i = 0; i < n; i++) sum += Math.max(left[i], right[i]); // satisfy both13        return sum;14    }15}

Same idea, in place. The second pass keeps the first pass's value with max.

Pass 1 left to right.
Pass 2 right to left: candies[i] = max(candies[i], candies[i+1] + 1).
Sum.

timeO(n)

Two passes + a sum.

spaceO(n)

One array (there is also an O(1) slope-counting trick).

javajava.util.*

1class Solution {2    public int candy(int[] ratings) {3        int n = ratings.length;4        int[] candies = new int[n];5        Arrays.fill(candies, 1);6        for (int i = 1; i < n; i++)                         // pass 1: left to right7            if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;8        for (int i = n - 2; i >= 0; i--)                    // pass 2: right to left, keep pass 1's gains9            if (ratings[i] > ratings[i + 1]) candies[i] = Math.max(candies[i], candies[i + 1] + 1);10        int sum = 0;11        for (int c : candies) sum += c;12        return sum;13    }14}

in the room

How to say it in the interview

talk track

Say "each child has two constraints that don't interact, so one pass per direction." Then explain why max is both necessary and enough.

traps

Giving equal ratings equal candies. There's no such rule, and it wastes candy.
Overwriting pass 1 in pass 2 without max.

what they ask next

Follow-ups

O(1) extra space?

Count the lengths of up-slopes and down-slopes and add arithmetic series, giving the peak max(up, down). It's tricky to get right, so mention it, but the two-pass version is the expected answer.

before you submit

Edge cases to test

One child → 1.
All equal [2,2,2] → 3: equal neighbours have no rule.
Strictly falling [4,3,2,1] → 10: only the right-to-left pass does any work.
A 50,000-child mountain (0..24,999 then 24,999..0) → 625,025,000 candies: still fits in an int.

practise next