Candy

There are n children standing in a line, each with a rating value. You are handing out candies under two rules:

Every child gets at least one candy.
A child with a higher rating than an adjacent neighbor gets more candies than that neighbor.

Return the minimum total number of candies you must give out.

Hints

· Stuck? Reveal one nudge at a time.

Each child has two neighbors — can one left-to-right pass respect both?

Do two passes: one left-to-right for left neighbors, one right-to-left for right neighbors.

Combine them by taking the maximum requirement at each child.

Common doubts

Going left to right, you don't yet know a child's right neighbor's final candy count. A second pass in the opposite direction supplies that side.

The left pass may have already given a child a high value to beat its left neighbor. The right pass must not lower that, so it takes the larger of the existing value and (right neighbor + 1).

No rule applies between equal ratings, so neither child is forced to have more than the other — they can both stay low, which minimizes the total.

Interview follow-ups

· What an interviewer asks next.

Yes — a single pass can track the lengths of the current increasing and decreasing runs and add the candy contributions arithmetically, avoiding the candies array.

The wrap-around creates a cyclic dependency that a simple two-pass can't resolve directly; you'd detect and break the cycle or iterate to a fixed point.

Fun facts

This two-pass 'reconcile both directions' pattern also computes, for each element, the span to the next greater element on each side.
Candy is a favorite hard-tagged interview greedy precisely because the naive one-pass attempt looks right but silently undercounts.

Asked at

AmazonGoogleMicrosoftUber

Frequently Sometimes Occasionally

Example 1

Input: ratings = [1,0,2]
Output: 5
Give 2, 1, 2 candies to the three children respectively.

Example 2

Input: ratings = [1,2,2]
Output: 4
Give 1, 2, 1 candies. The last two children have equal ratings, so the third can get just one.

Constraints

- n == ratings.length - 1 <= n <= 2 * 10^4 - 0 <= ratings[i] <= 2 * 10^4

Each child has two neighbors, and a single sweep can only respect one side. So make two passes: a left-to-right pass fixes every "higher than my left neighbor" rule, a right-to-left pass fixes every "higher than my right neighbor" rule, and taking the larger of the two requirements at each child satisfies both at once.

Prerequisites

Before you start

· Concepts used directly in the solution.

Local constraints. Each rule involves only a child and one neighbor at a time.

Two-directional sweeps. Resolving left-side and right-side constraints in separate passes, then combining.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rules

“Does every child get at least one candy?”

Yes — the minimum any child receives is one.

“What about equal adjacent ratings?”

No constraint — equal neighbors can get different candy counts, so each may stay at the minimum.

Goal

“Am I minimizing the total?”

Yes — satisfy the rules with the fewest candies overall.

The ideal opening — say it like this

Each child has a left and a right neighbor, so one pass can't handle both sides.

I'll do a left-to-right pass so anyone rated higher than their left neighbor gets one more than them.

Then a right-to-left pass does the same for the right neighbor, taking the max so both rules hold.

Understand the problem

Worked example — ratings = [1, 3, 2, 2, 1]

start:        1 1 1 1 1
left->right:  1 2 1 1 1     (index 1 rated > index 0)
right->left:  1 2 1 2 1     (index 3 > index 4; index 1 already 2 >= 2)
total = 1 + 2 + 1 + 2 + 1 = 7

Key observations

1Aha

One pass can only see one neighbor

A left-to-right pass enforces "more than my left neighbor" but can't know about the right neighbor yet. You need a second pass in the opposite direction.

2Aha

Combine passes with a max

After the left pass, the right pass sets each child to max(current, rightNeighbor + 1) when its rating is higher on the right. The max keeps the left-side requirement intact while adding the right-side one.

3Aha

Equal ratings reset the run

No rule applies between equal neighbors, so a child no higher than either neighbor can stay at one — which is what keeps the total minimal.

Brute force vs optimal

	Relax until stable	Two passes
Idea	Repeatedly bump any child violating a neighbor rule	Left-to-right then right-to-left, take the max
Time	O(n^2)	O(n)
Space	O(n)	O(n)

The relaxation approach re-sweeps until nothing changes; the two directed passes reach the same assignment in linear time. Full code is in the Approaches selector below.

Summary

Key takeaway

Give everyone one candy, then do two passes: left-to-right so each child beats its left neighbor, and right-to-left taking the max so each also beats its right neighbor. Two O(n) passes give the minimum total that satisfies both sides.

candies = [1] * n
for i in 1..n-1:  if ratings[i] > ratings[i-1]: candies[i] = candies[i-1] + 1
for i in n-2..0:  if ratings[i] > ratings[i+1]: candies[i] = max(candies[i], candies[i+1] + 1)
return sum(candies)