Problem 33.5 · Greedy AlgorithmsHard

Candy

What it teaches: Two passes for constraints from both neighbours.

Practise it on judges as “Candy”.

The problem

Each child gets at least one candy, and a child with a higher rating than a neighbour gets more candy than that neighbour. Return the minimum total.

Example 1

Input: ratings = [1, 0, 2]
Output: 5

2, 1, 2.

Constraints

1 ≤ n ≤ 2 × 10⁴

Pattern clues in the wording

→ Each element constrained by left and right neighbours

These clues point to Greedy Choice: Make the best-looking choice at each step and never undo it, after proving that this choice is always safe.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int candy(int[] ratings) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	ratings = [1,0,2]	5
2	ratings = [1,2,2]	4

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Two passes · O(n)

Two passes

Time O(n) Space O(n)

Start with 1 each. Left to right, then right to left with max. Sum.

Approach 1

import java.util.Arrays;

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] c = new int[n];
        Arrays.fill(c, 1);
        for (int i = 1; i < n; i++) if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1;
        for (int i = n - 2; i >= 0; i--) if (ratings[i] > ratings[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
        int total = 0;
        for (int x : c) total += x;
        return total;
    }
}

Verdict: Each pass enforces one side without breaking the other.

Before you submit

Edge cases and common mistakes

Test these inputs

Equal neighbours (no constraint)
Strictly decreasing ratings

Mistakes people make

Giving equal ratings equal candy (not required).

Interview

Follow-up questions

Can it use O(1) extra space?

Command Palette

The problem

Approaches

Two passes

Edge cases and common mistakes

Follow-up questions