PPractick

The problem

A teacher hands out candies to children standing in a line, each with a rating. Every child gets at least one candy, and a child with a higher rating than an immediate neighbour must get more candies than that neighbour. What's the minimum total? The constraints point in two directions, so handle them in two passes. A left-to-right pass enforces "more than the left neighbour when rated higher". A right-to-left pass enforces the same for the right neighbour, taking the maximum so the first pass's constraints still hold.

Example: ratings [1, 0, 2] → 5 (candies 2, 1, 2).

Function signature

long long candy(const vector<int>& ratings);

Test cases

Input	Output	Explanation
[1, 0, 2]	5	2, 1, 2
[1, 2, 2]	4	1, 2, 1: equal neighbours need nothing
[1, 3, 2, 2, 1]	7	1, 2, 1, 2, 1
[5, 4, 3, 2, 1]	15	5, 4, 3, 2, 1
[1]	1

(Confirm: only strictly higher ratings than an adjacent child impose "more candy"; equal ratings impose nothing.)

How interviewers phrase it

• "There are n children standing in a line, each with a rating. Each child gets at least one candy, and children with a higher rating get more candies than their neighbours. Return the minimum number of candies" (LeetCode 135).

Clarifying questions to ask

1. Do equal neighbours need equal candies? (No, there's no constraint between them.)
2. Is "higher" strict? (Yes.)
3. How large is n? (Up to 2·10⁴; the answer fits in 32 bits, but 64-bit is safe.)

Follow-ups to expect

1. "Why two passes?"
2. "Why take the max in the second pass?"
3. "Can it be done in O(1) extra space?"
4. "Why is this the minimum?"
5. "Complexity?"

Related questions

• Kadane's Algorithm Medium
• Stock Buy and Sell Easy
• Capacity to Ship Packages Within D Days Medium
• Assign Cookies Easy
• Lemonade Change Easy
• Jump Game - I Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in