Candy

HARD✓ CHIP-TIMEDLC #135 — FULL STATEMENT ↗

The drill: Children stand in a line, each with a rating. Hand out the fewest candies so everyone gets at least one, and any child rated higher than a neighbor gets strictly more candy than that neighbor. Return the total handed out.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Children stand in a single line, each holding a rating number. Candy gets handed out one pile per child, and every child must receive at least one candy no matter what.

Whenever a child's rating is higher than an immediate neighbor's, that child's pile has to be strictly bigger than that neighbor's pile — this applies independently to the left neighbor and the right neighbor, wherever they exist.

Equal ratings between neighbors carry no such requirement — their piles can be equal or different. The task is minimizing the total candy handed out while keeping every rule satisfied, and reporting that total.

EX 01

ratings = [1, 0, 2]

→ 5

VALLEY IN THE MIDDLE

EX 02

ratings = [1, 2, 2]

→ 4

TIE RESETS THE CLIMB

EX 03

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

→ 7

PEAK THEN A TIE THEN A DESCENT

every child receives at least one candy, no exceptions
a higher-rated child beats each lower-rated neighbor's candy count
equal-rated neighbors have no ordering requirement between their piles
the total handed out should be the smallest amount that satisfies every rule

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Each child's candy count only has to beat the neighbors it actually outranks — a purely local rule. What goes wrong if you try to satisfy both neighbors in a single combined pass?

HINT 2 THE STRUCTURE

Split the constraint in two: 'beats the left neighbor' and 'beats the right neighbor' are each satisfiable on their own with one directional sweep.

HINT 3 ONE STEP FROM THE ANSWER

Sweep left to right, bumping a child above its left neighbor only when its rating is higher. Then sweep right to left doing the same against the right neighbor, taking the max with what's already there. Sum the result.

COACH'S BOARD — THE PATTERN, STEP BY STEP

TWO SWEEPS, TAKE THE MAXPATTERN · GREEDY — TWO-PASSratings = [1, 3, 2, 2, 1]

CANDIES

candies → [1, 1, 1, 1, 1]

STEP 1

Ratings [1,3,2,2,1]. Everyone starts with 1 candy — a left sweep enforces beating the left neighbor, a right sweep enforces beating the right.

STEP 1 / 10 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/candy.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)
        return sum(candies)

TIME O(N)SPACE O(N)PYTHON · RACE PACE · 11 LN

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n
        changed = True
        while changed:
            changed = False
            for i in range(n):
                if i > 0 and ratings[i] > ratings[i - 1] and candies[i] <= candies[i - 1]:
                    candies[i] = candies[i - 1] + 1
                    changed = True
                if i < n - 1 and ratings[i] > ratings[i + 1] and candies[i] <= candies[i + 1]:
                    candies[i] = candies[i + 1] + 1
                    changed = True
        return sum(candies)

TIME O(N²)SPACE O(N)PYTHON · TRAINING PACE · 15 LN

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

TIME O(N)SPACE O(N)JAVA · RACE PACE · 20 LN

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);
        boolean changed = true;
        while (changed) {
            changed = false;
            for (int 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;
                }
            }
        }
        int total = 0;
        for (int c : candies) total += c;
        return total;
    }
}

TIME O(N²)SPACE O(N)JAVA · TRAINING PACE · 24 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED