Shubham Sourabhthe room · director's cutplain résumé
Room 04 · The Grind — Greedy

Candy

HARD✓ CHIP-TIMEDLC #135 — FULL STATEMENT

The briefingthe full drill, in my own words

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.

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.

  • 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
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

The hintstake 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 boardthe pattern, step by step

TWO SWEEPS, TAKE THE MAXPATTERN · GREEDY — TWO-PASSratings = [1, 3, 2, 2, 1]
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 splitstwo 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

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