Candy

LeetCode 135 • Hard • Arrays

Input: ratings = [1,0,2] → Output: 5 (candies 2,1,2). Two passes: left-to-right then right-to-left.

TimeO(n)

SpaceO(n)

pass: — candies: —

Left pass

Right pass

pass—

i—

candies—

Speed:

Ready

Press Play. Two passes: left-to-right (right neighbor gets more), right-to-left (left neighbor gets more).

Whiteboard

Size:3

Type It

Practice until you don't need to look. Two passes: left-to-right, then right-to-left.

═══ CANDY — TWO PASSES ═══

PATTERN ▸ Two passes (L→R then R→L) O(n) · O(n)

① INIT

candies = [1] * n

② PASS 1: LEFT TO RIGHT

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

③ PASS 2: RIGHT TO LEFT

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

④ RETURN

return sum(candies)

your implementation

Verify: