← Create New Paste

The Candy Distribution Problem: Why Two Passes Beat One Clever Loop in Coding Interviews

3 views
"Candy" (children in a line with ratings; each child gets at least one candy, and a child with a higher rating than a neighbor must get more than that neighbor; minimize the total) is a favorite interview problem because the obvious one-pass idea fails, and the fix teaches a reusable pattern. Clarify first Ask: are equal ratings allowed, and does an equal neighbor impose any constraint? (Usually no: equal neighbors can get any amounts.) Can the array be empty? What is the maximum length? Stating these early avoids rewriting later. Why a single left-to-right pass fails If you go left to right and give child i one more than child i-1 whenever rating[i] > rating[i-1], you handle increasing runs. But on a decreasing run like [5, 4, 3], you would give 1, 1, 1, which breaks the rule for the left children. Each child actually has two constraints, one from each neighbor, and one pass only sees one direction. The two-pass solution 1. Initialize candies = [1] * n. 2. Left pass: for i from 1 to n-1, if rating[i] > rating[i-1], set candies[i] = candies[i-1] + 1. 3. Right pass: for i from n-2 down to 0, if rating[i] > rating[i+1], set candies[i] = max(candies[i], candies[i+1] + 1). 4. Return the sum. The max in the right pass is the key line: it keeps whatever the left pass required while adding the right-side requirement. Time O(n), space O(n). Dry run Ratings [1, 0, 2]: left pass gives [1, 1, 2]; right pass raises index 0 to 2, giving [2, 1, 2], total 5. Ratings [1, 2, 2]: left pass [1, 2, 1]; right pass changes nothing; total 4. Walking through one strictly decreasing case and one with equal neighbors shows the interviewer you checked both constraint directions. The O(1) space follow-up Strong candidates mention that you can count lengths of increasing and decreasing slopes in one pass and sum arithmetic series, adjusting the peak to the larger of the two slopes. You do not always need to code it, but explaining the idea shows depth. The reusable lesson "Satisfy the constraint from the left, then from the right, and take the max" also solves problems like trapping water bounds and product-of-neighbors variants. Naming the pattern out loud helps the interviewer follow your reasoning. Practicing under real conditions This problem rewards calm thinking: noticing the counterexample, explaining why the first idea fails, and fixing it. If you want support during the real interview, Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, helping you stay structured while you think out loud.
Created Nov 17, 2026 07:30 Expires Nov 17, 2027 07:30