Two-sided max walls

1 min 7 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

Bars of heights 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 stand side by side and it rains. How much water sits in the dips? Over a single bar the water rises until it would spill over the tallest wall on its left or the tallest wall on its right, whichever is lower. So the water above bar i is

water[i] = min(tallest on the left, tallest on the right) − height[i], or 0 if that is negative

By hand you would, for each bar, scan left for the tallest and scan right for the tallest. That is two scans of up to n per bar, O(n²). The two-sweep version (store leftMax and rightMax arrays first) brings it to O(n) time with O(n) extra memory. The question is whether we can drop the arrays.

Build the structure, one piece at a time

Piece one: two pointers, l at the left end and r at the right end, and two running numbers, leftMax and rightMax, the tallest bar seen so far from each side. These replace the two arrays.

Piece two, the key idea: we do not need both maxima exactly, only the smaller one, and we can know which side is smaller without seeing the whole array. If leftMax < rightMax, the water at bar l is decided: its true right wall is at least rightMax, which is already bigger than leftMax, so the minimum is leftMax no matter what lies between. Settle bar l and move l right. Otherwise settle bar r and move r left.

The walk continues until the pointers meet; the total for this example is 6. Each step settles exactly one bar, updating that side's running max first (so a bar that is itself the new tallest gets 0 water).

Why it is correct

The invariant: every bar outside [l, r] has had its water computed correctly, and leftMax, rightMax are the true maxima of the bars left of l and right of r (inclusive of the ends we have processed). The claim that needs proof is that settling bar l with water leftMax − height[l] is exact when leftMax < rightMax. The true right wall of bar l is the maximum over everything to its right, which includes the bars at and beyond r, so

trueRight[l] ≥ rightMax > leftMax = trueLeft[l]

and therefore min(trueLeft, trueRight) = leftMax. The mirror holds for the right side when rightMax ≤ leftMax. So each settled bar gets exactly the by-hand formula's value.

Why it is fast

Each step moves one pointer inward by one, so there are at most n steps, each a comparison, a max update and a subtraction: O(n) time. Memory is four numbers, O(1), where the two-array version needed 2n extra cells. The original by-hand method was O(n²).

How to recognise it in an interview

Cues: "water trapped", "bounded by the smaller of the two sides", or any per-position value of the form min(best on the left, best on the right). If the question is a maximum over pairs instead of a sum over positions, it is the Container With Most Water variant of the same walk.

Say: "The water at a bar depends on the smaller side's maximum, so I will move the pointer on the smaller side; that bar's answer is already decided." Trapping Rain Water is the example. Container With Most Water moves the shorter wall for the same reason: the shorter wall caps every container it could form. Trapping Rain Water II is the 2-D version, where "the smaller side" becomes "the lowest point on the boundary" and the pointers become a min-heap.

02The idea in one line

Water at i is bounded by the smaller side's running max; advance the smaller side.

Reach for it when: Trapping rain water, container variants, two-sided bounds.

Cost: O(n) time, O(1) space.

03The walk-through, step by step

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

1. Water at i = min(max to the left, max to the right) − h[i]
2. Two pointers from the ends; each side remembers its max wall so far
3. h[l]=0 < h[r]=1: left side is the bound. water += 0 − 0 = 0
4. h[r]=1 ≤ h[l]=1: right side is the bound. water += 1 − 1 = 0
5. h[l]=1 < h[r]=2: left side is the bound. water += 1 − 1 = 0
6. h[l]=0 < h[r]=2: left side is the bound. water += 1 − 0 = 1
7. h[r]=2 ≤ h[l]=2: right side is the bound. water += 2 − 2 = 0
8. h[r]=1 ≤ h[l]=2: right side is the bound. water += 2 − 1 = 1
9. h[r]=2 ≤ h[l]=2: right side is the bound. water += 2 − 2 = 0
10. h[l]=2 < h[r]=3: left side is the bound. water += 2 − 2 = 0
11. h[l]=1 < h[r]=3: left side is the bound. water += 2 − 1 = 1
12. h[l]=0 < h[r]=3: left side is the bound. water += 2 − 0 = 2
13. h[l]=1 < h[r]=3: left side is the bound. water += 2 − 1 = 1
14. Pointers meet: total water 6
15. The smaller side's max is already final, so one pass suffices: O(n), O(1) space

04Asked at Google

3 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 Two Pointers: Opposite ends converge, Fix one, two-pointer the rest, Reader / writer pointers, Dutch national flag partition, Merge two sorted sequences.