Facilities models a warehouse roof as unit-width bays. After a storm, ops needs how many cubic units of standing water sit in the valleys before the pumps catch up. The first version, for every bay, scanned left for the tallest parapet and right for the other. Forty bays were instant. A kilometer of unit sections was still looping when the work order timed out.

Trapping Rain Water asks how much water sits on top of each bar. An array already gives height[i]. Nested peak scans use that and still pay O(n²). Opposite-end two pointers keep a running left max and right max so each index is decided once. Water at i is the lower of those two skylines, minus height[i].

This is an interview writeup, not a procedure lecture. The two pointers post owns the left/right walk. Here we only care about which skyline is the bottleneck. Container With Most Water is a different geometry: one rectangle between two lines, height of the shorter wall times the gap. This prompt fills on top of every bar, bounded by the tallest bar to its left and to its right.

The problem

Given an int[] height of non-negative bar heights, each bar has width 1. After rain, water sits on top of a bar only where a wall exists somewhere on the left and somewhere on the right. Return the total units trapped. Water at index i is min(leftMax, rightMax) - height[i], or 0 if that difference is not positive. leftMax is the tallest bar in 0..i; rightMax is the tallest in i..n-1.

height = [3, 0, 1, 0, 4, 0, 2]  →  10
height = [2, 0, 2]              →  2
height = [4, 4, 4]              →  0

On the first row, index 1 (0) sits under min(3, 4) so it holds 3. Index 2 (1) holds 2. Index 3 (0) holds 3. Index 5 (0) sits under min(4, 2) so it holds 2. The two peaks and both ends hold nothing: an end is missing one skyline.

Note: Container With Most Water asks for the largest single rectangle two walls can form. Do not recycle that short-wall proof. Rain water sums a column per index.

Nested peak scans are the honest brute force

For each i, walk left for the max, walk right for the max, add min - height[i]. Both scans include i, so the difference is never negative. Correct. Quadratic.

int trapNested(int[] height) {
    int n = height.length;
    int water = 0;
    for (int i = 0; i < n; i++) {
        int leftMax = 0;
        for (int j = 0; j <= i; j++) {
            leftMax = Math.max(leftMax, height[j]);
        }
        int rightMax = 0;
        for (int j = i; j < n; j++) {
            rightMax = Math.max(rightMax, height[j]);
        }
        water += Math.min(leftMax, rightMax) - height[i];
    }
    return water;
}

At n = 20 this is a rounding error. At a kilometer of bays you paid two nested scans for a question two pointers answer in one pass: which skyline is lower right now?

Two extra arrays of prefix and suffix maxima make the same formula linear in time and linear in space. Interviewers then ask you to drop the arrays.

Two pointers carry both skylines

Start lo at 0 and hi at n - 1. Track leftMax and rightMax as the tallest bars seen from each end. While lo <= hi, compare the two running maxima.

If leftMax <= rightMax, the left index is fully determined: some bar on or past hi is at least rightMax, so the bottleneck is the left skyline. Raise leftMax with height[lo] if needed, add leftMax - height[lo], then lo++. Otherwise do the symmetric step on hi.

Process the lower skyline. That running max is the min in min(leftMax, rightMax) for the index you are about to settle. Moving the other pointer would throw away a wall you have not finished using.

Walk [3, 0, 1, 0, 4, 0, 2] from the ends. L and R are the running maxima, not the bar under the pointer:

lo=0 hi=6  L=0 R=0   L<=R  raise L=3  add 0   lo→1   water=0
lo=1 hi=6  L=3 R=0   L>R   raise R=2  add 0   hi→5   water=0
lo=1 hi=5  L=3 R=2   L>R   h[5]=0     add 2   hi→4   water=2
lo=1 hi=4  L=3 R=2   L>R   raise R=4  add 0   hi→3   water=2
lo=1 hi=3  L=3 R=4   L<=R  h[1]=0     add 3   lo→2   water=5
lo=2 hi=3  L=3 R=4   L<=R  h[2]=1     add 2   lo→3   water=7
lo=3 hi=3  L=3 R=4   L<=R  h[3]=0     add 3   lo→4   water=10
lo > hi, stop

Index 4 (4) is the right-hand peak; it was used to raise R and never needed a column of its own. Total 10 matches the nested scan.

The Java is that walk:

int trap(int[] height) {
    int lo = 0;
    int hi = height.length - 1;
    int leftMax = 0;
    int rightMax = 0;
    int water = 0;
    while (lo <= hi) {
        if (leftMax <= rightMax) {
            leftMax = Math.max(leftMax, height[lo]);
            water += leftMax - height[lo];
            lo++;
        } else {
            rightMax = Math.max(rightMax, height[hi]);
            water += rightMax - height[hi];
            hi--;
        }
    }
    return water;
}

Time is O(n) — each index is processed once. Space is O(1) besides the two indexes and the two running maxima.

Note: Stay on lo <= hi. This update order still owes the last index a column; lo < hi skips it and undercounts. Empty input: hi is -1 and the loop never runs. All equal heights add 0. Switch the accumulator to long if they widen the type.

What interviewers usually poke next

  • Why not the container proof? Container With Most Water moves the short wall because width shrinks and you want one rectangle. Here you process the side with the lower skyline because that min is the water cap for that index. Same two pointers, different invariant. Do not mix them.
  • Prefix / suffix arrays. Legal O(n) time, O(n) extra. Say why the two-pointer squeeze is the same formula without the arrays.
  • Monotonic stack of indices. Push indexes while bars are non-increasing. A strictly taller bar is a right wall; pop the valley and fill using the new stack top as the left wall. Width is the gap between walls; height is min of the two walls minus the popped bar. Linear time, O(n) extra. The stack post owns LIFO; here the stack only stores indexes. Mention it; the intended bill on this prompt is still O(1) extra space.
  • Negatives / overflow. The prompt is non-negative; a negative bar is undefined — ask. Switch the accumulator to long if they widen the type.

You are done with this problem when you can say, out loud, why nested peak scans are correct, why the lower skyline decides the next index, and why this is not the one-rectangle container problem.