Two-pass neighbour constraints

38 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Children stand in a line with ratings [1, 0, 2, 2, 1]. Each child must get at least one sweet, and a child with a higher rating than a neighbour must get more sweets than that neighbour. What is the fewest sweets in total?

By hand you might give everyone one sweet, then walk along fixing problems: the 1 next to the 0 needs more, the 2 next to the 0 needs more, then the second 2 is next to a 1 that is lower, so the 2 needs more, and raising one child can break a rule with the neighbour on the other side, so you walk again. Each walk may fix something that undoes an earlier fix, and it is not obvious when to stop or whether the total is minimal.

Build the structure, one piece at a time

The trick is to split the rule into two one-directional rules and satisfy them in two separate passes over an array of sweets, starting from all 1s.

1. Left-to-right pass handles "higher than the left neighbour": if r[i] > r[i−1], set c[i] = c[i−1] + 1. After this pass: ratings [1, 0, 2, 2, 1] give sweets [1, 1, 2, 1, 1]. (0 is not above 1; 2 is above 0, so 2; the second 2 is not above 2; 1 is not above 2.)
2. Right-to-left pass handles "higher than the right neighbour": if r[i] > r[i+1], set c[i] = max(c[i], c[i+1] + 1). Walking back: the second 2 is above the 1, so it becomes max(1, 2) = 2; the first 2 is not above the second 2; the 0 is not above 2; the first 1 is above the 0, so it becomes max(1, 2) = 2.

Final sweets [2, 1, 2, 2, 1], total 8. The structure is one array visited twice, and the maximum in the second pass is what stops the second pass from undoing the first.

Why it is correct

After the left-to-right pass, every "higher than the left neighbour" rule holds, and each value is the smallest that satisfies the rules to its left, because it is exactly one more than its left neighbour whenever it must be more, and 1 otherwise. In the right-to-left pass a value only ever increases, to the smallest amount that satisfies its right neighbour, so no left rule breaks: if c[i] was more than c[i−1] it still is, and c[i−1] itself will be raised only if its own right rule demands it. At the end both one-directional rules hold, so the full rule holds. Minimality: every child's final amount is forced, since it equals the longer of the strictly increasing run of ratings ending at it from the left and the one from the right, and any valid assignment must give at least that many.

c[i] = max( 1 + length of the rising run arriving from the left, 1 + length of the rising run arriving from the right )

Why it is fast

Two passes, each a comparison and an assignment per child: O(n) time and one extra array of size n. The fix-until-stable walk could need many passes, up to the length of the longest rising run, which is O(n²) in the worst case.

How to recognise it in an interview

Cues: a rule that compares each element with both neighbours, or an answer at each position that depends on everything to its left and everything to its right. Say: I will satisfy the left-side rule in one pass and the right-side rule in a second pass, combining with a maximum. Candy is the example. Trapping Rain Water keeps the maximum height seen from the left and from the right and takes the smaller at each bar. Product of Array Except Self multiplies a left-prefix product by a right-suffix product.

02The idea in one line

Left-to-right fixes one side's rule, right-to-left fixes the other; take the max.

Reach for it when: Candy, trapping rain water (two arrays), product except self, minimum cost tree.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Candy on ratings [1,0,2]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Start everyone at 1 candy; fix the left rule, then the right rule
2. left→right: 0 ≤ 1, candy[1] stays 1
3. left→right: 2 > 0, so candy[2] = candy[1] + 1 = 2
4. left→right: 2 ≤ 2, candy[3] stays 1
5. left→right: 1 ≤ 2, candy[4] stays 1
6. right→left: 2 > 1: candy[3] = max(own, candy[4] + 1) = 2
7. right→left: 2 ≤ 2, candy[2] unchanged
8. right→left: 0 ≤ 2, candy[1] unchanged
9. right→left: 1 > 0: candy[0] = max(own, candy[1] + 1) = 2
10. Both rules hold everywhere with minimal values: total = 8
11. Two linear passes: O(n) time, one extra array

04Asked at Google

4 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Greedy: Furthest reach (jump game), Sort, then take greedily, Reset-on-negative sweep, Last-occurrence partition, Counting-based greedy (small alphabet), Two-pointer assignment after sorting.