Trapping Rain Water: from O(n) space to O(1) with two pointers

height = [0,1,0,2,1,0,1,3,2,1,2,1] — draw the bars, shade the water, the answer is 6. The picture makes it look like a geometry problem. It is actually a question about what a single cell knows: at position i, how high can the water sit? The water level is pinned by the shorter of the two walls containing it — the tallest bar to the left and the tallest bar to the right. Everything else follows from that.

The formula one cell at a time

For every position i, the water trapped above it is:

water[i] = max(0, min(left_max[i], right_max[i]) - height[i])

left_max[i] is the maximum height in height[0..i]. right_max[i] is the maximum height in height[i..n-1]. The cell itself is part of both — so neither max is ever zero when a bar exists. Summing water[i] across all positions gives the answer. This formula is the spine of every solution. The approaches differ only in how efficiently they compute left_max and right_max.

What the constraints force

n goes up to 20 000 and each height up to 100 000. O(n²) at 400 million operations is borderline painful on a 20 000-element input. O(n) is the actual target. The height ceiling does not affect algorithm choice, but it matters for overflow: in C#, up to 20 000 cells each holding up to 100 000 units of water gives a theoretical maximum near 2 × 10^9, which just fits in a 32-bit signed integer. I'd reach for long if the problem were scaled up.

The constraint that actually shapes the algorithm is the implication you draw from n <= 2 * 10^4: you can afford O(n) extra space (two arrays of 20 000 integers is trivial), so the prefix/suffix precomputation approach is viable. The deeper question is whether you can eliminate even that — and the two-pointer approach answers yes, at the cost of a harder correctness argument.

Arrays shorter than 3 elements cannot trap water. The edge cases that produce zero immediately: n < 3, all-zeros input, monotone arrays (no valley to fill). All four approaches handle these without explicit guards — the accumulation simply produces nothing.

Approach 1: brute force — O(n²) time, O(1) space

For each position, scan left to find left_max, scan right to find right_max, apply the formula.

class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)
        total = 0
        for i in range(1, n - 1):
            left_max = max(height[:i+1])
            right_max = max(height[i:])
            total += max(0, min(left_max, right_max) - height[i])
        return total

public class Solution {
    public int Trap(int[] height) {
        int n = height.Length;
        int total = 0;
        for (int i = 1; i < n - 1; 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]);
            total += Math.Max(0, Math.Min(leftMax, rightMax) - height[i]);
        }
        return total;
    }
}

Trace on height = [4, 2, 0, 3, 2, 5] — just the non-trivial interior positions:

i=1: left_max=max(4,2)=4, right_max=max(2,0,3,2,5)=5 -> min(4,5)-2 = 2
i=2: left_max=max(4,2,0)=4, right_max=max(0,3,2,5)=5 -> min(4,5)-0 = 4
i=3: left_max=max(4,2,0,3)=4, right_max=max(3,2,5)=5 -> min(4,5)-3 = 1
i=4: left_max=max(4,2,0,3,2)=4, right_max=max(2,5)=5 -> min(4,5)-2 = 2
total = 2 + 4 + 1 + 2 = 9

Correct. But the work is redundant. left_max at position 3 recomputes everything already seen at position 2. Every iteration throws away the running max from the previous one.

Approach 2: prefix/suffix arrays — O(n) time, O(n) space

Precompute. One left-to-right pass fills left_max. One right-to-left pass fills right_max. One final pass accumulates water. Three O(n) loops; no work ever repeated.

Full hand trace on height = [0,1,0,2,1,0,1,3,2,1,2,1]:

Step 1 — build left_max (left to right, each cell = max seen so far including itself):
  i=0:  left_max[0] = height[0] = 0
  i=1:  left_max[1] = max(0, 1) = 1
  i=2:  left_max[2] = max(1, 0) = 1
  i=3:  left_max[3] = max(1, 2) = 2
  i=4:  left_max[4] = max(2, 1) = 2
  i=5:  left_max[5] = max(2, 0) = 2
  i=6:  left_max[6] = max(2, 1) = 2
  i=7:  left_max[7] = max(2, 3) = 3
  i=8..11: all 3 (3 dominates)
  -> left_max = [0,1,1,2,2,2,2,3,3,3,3,3]

Step 2 — build right_max (right to left):
  i=11: right_max[11] = height[11] = 1
  i=10: right_max[10] = max(1, 2) = 2
  i=9:  right_max[9]  = max(2, 1) = 2
  i=8:  right_max[8]  = max(2, 2) = 2
  i=7:  right_max[7]  = max(2, 3) = 3
  i=6..0: all 3
  -> right_max = [3,3,3,3,3,3,3,3,2,2,2,1]

Step 3 — accumulate (water = max(0, min(L, R) - h)):
  i=0:  min(0,3)-0 = 0
  i=1:  min(1,3)-1 = 0
  i=2:  min(1,3)-0 = 1  ***
  i=3:  min(2,3)-2 = 0
  i=4:  min(2,3)-1 = 1  ***
  i=5:  min(2,3)-0 = 2  ***
  i=6:  min(2,3)-1 = 1  ***
  i=7:  min(3,3)-3 = 0
  i=8:  min(3,2)-2 = 0
  i=9:  min(3,2)-1 = 1  ***
  i=10: min(3,2)-2 = 0
  i=11: min(3,1)-1 = 0
  total = 1+1+2+1+1 = 6 ✓

class Solution:
    def trap(self, height: list[int]) -> int:
        n = len(height)
        left_max = [0] * n
        right_max = [0] * n
 
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])
 
        right_max[n - 1] = height[n - 1]
        for i in range(n - 2, -1, -1):
            right_max[i] = max(right_max[i + 1], height[i])
 
        total = 0
        for i in range(n):
            total += max(0, min(left_max[i], right_max[i]) - height[i])
        return total

public class Solution {
    public int Trap(int[] height) {
        int n = height.Length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];
 
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++)
            leftMax[i] = Math.Max(leftMax[i - 1], height[i]);
 
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--)
            rightMax[i] = Math.Max(rightMax[i + 1], height[i]);
 
        int total = 0;
        for (int i = 0; i < n; i++)
            total += Math.Max(0, Math.Min(leftMax[i], rightMax[i]) - height[i]);
        return total;
    }
}

This is the version I reach for when I want code that is easy to read and easy to verify. The three passes each have an obvious invariant. Time is O(n) — optimal, since you must inspect every bar at least once. The only cost is the two auxiliary arrays: O(n) space.

For a 20 000-element input in C#, two int[] of 20 000 each is 160 KB. Nothing. But the question of whether you can do better exists, and the two-pointer approach answers it.

Approach 3: monotonic stack — O(n) time, O(n) space

The stack approach thinks differently. Instead of asking "how much water sits above position i?" per column, it asks "when does a bounded horizontal layer of water close?" It processes water in horizontal slabs rather than vertical columns.

The stack stores indices in decreasing height order (monotonically decreasing). When we see a bar taller than the current stack top, a water pocket has just closed on the right — the current bar is the right wall, the stack top is the bottom, and the element below it in the stack is the left wall.

Hand trace on height = [0,1,0,2,1,0,1,3,2,1,2,1], selected steps:

i=0, h=0: stack=[] -> push 0. stack=[0]
i=1, h=1: h > height[0]=0
  pop bottom=0 (height=0), stack now empty -> no left wall, break
  push 1. stack=[1]
i=2, h=0: h <= height[1]=1 -> push 2. stack=[1,2]
i=3, h=2: h > height[2]=0
  pop bottom=2 (height=0), left=stack[-1]=1 (height=1)
  width = 3-1-1 = 1, water_height = min(1,2)-0 = 1 -> add 1*1 = 1
  h > height[1]=1
  pop bottom=1 (height=1), stack now empty -> break
  push 3. stack=[3]
i=4, h=1: h <= height[3]=2 -> push 4. stack=[3,4]
i=5, h=0: push 5. stack=[3,4,5]
i=6, h=1: h > height[5]=0
  pop bottom=5 (height=0), left=4 (height=1)
  width=6-4-1=1, water_height=min(1,1)-0=1 -> add 1
  h <= height[4]=1 -> push 6. stack=[3,4,6]
i=7, h=3: h > height[6]=1
  pop bottom=6 (height=1), left=4 (height=1)
  width=7-4-1=2, water_height=min(1,3)-1=0 -> add 0
  h > height[4]=1
  pop bottom=4 (height=1), left=3 (height=2)
  width=7-3-1=3, water_height=min(2,3)-1=1 -> add 3
  h > height[3]=2
  pop bottom=3 (height=2), stack now empty -> break
  push 7. stack=[7]
...continuing gives total = 6 ✓

class Solution:
    def trap(self, height: list[int]) -> int:
        stack = []
        total = 0
        for i, h in enumerate(height):
            while stack and h > height[stack[-1]]:
                bottom = stack.pop()
                if not stack:
                    break
                left = stack[-1]
                width = i - left - 1
                water_height = min(height[left], h) - height[bottom]
                total += width * water_height
            stack.append(i)
        return total

public class Solution {
    public int Trap(int[] height) {
        var stack = new Stack<int>();
        int total = 0;
        for (int i = 0; i < height.Length; i++) {
            while (stack.Count > 0 && height[i] > height[stack.Peek()]) {
                int bottom = stack.Pop();
                if (stack.Count == 0) break;
                int left = stack.Peek();
                int width = i - left - 1;
                int waterHeight = Math.Min(height[left], height[i]) - height[bottom];
                total += width * waterHeight;
            }
            stack.Push(i);
        }
        return total;
    }
}

The stack approach is O(n) time and O(n) space — the same asymptotic profile as prefix arrays, but it calculates water horizontally rather than vertically. It finds bounded containers as they close, rather than asking each cell how full it is. I would not reach for it in an interview unless explicitly asked about the stack variant — the mental model is harder to reconstruct under pressure. But it is worth understanding because the same horizontal-layer thinking solves Largest Rectangle in Histogram (84), which is this problem's mirror image.

The state machine of the stack is also easy to reason about as a flowchart:

Approach 4: two pointers — O(n) time, O(1) space

Here is the insight that makes the prefix/suffix arrays unnecessary. Look at the formula again:

water[i] = max(0, min(left_max[i], right_max[i]) - height[i])

The water at position i is determined by min(left_max[i], right_max[i]). The minimum of the two maxima. If left_max[i] < right_max[i], the left side is the binding constraint — it does not matter what right_max[i] is exactly, only that it is at least as large as left_max[i]. And if you are processing from the left with a pointer, and height[left] <= height[right], then right_max for the current left position is guaranteed to be at least height[right], which is at least height[left]. The right side is tall enough; the left side controls the water level.

That is the invariant: whichever pointer points to the shorter current bar, we can compute the water above it right now using only the running max from that side. We do not need to know the exact max from the other side — we only need to know it is at least as large, and the other pointer's current height guarantees that.

class Solution:
    def trap(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        left_max = right_max = 0
        total = 0
 
        while left < right:
            if height[left] <= height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    total += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    total += right_max - height[right]
                right -= 1
 
        return total

public class Solution {
    public int Trap(int[] height) {
        int left = 0, right = height.Length - 1;
        int leftMax = 0, rightMax = 0;
        int total = 0;
 
        while (left < right) {
            if (height[left] <= height[right]) {
                if (height[left] >= leftMax)
                    leftMax = height[left];
                else
                    total += leftMax - height[left];
                left++;
            } else {
                if (height[right] >= rightMax)
                    rightMax = height[right];
                else
                    total += rightMax - height[right];
                right--;
            }
        }
 
        return total;
    }
}

One pass. Four scalar variables. The two running maxima replace the two arrays — but only because we process positions in an order that guarantees the invariant holds at every step.

Full hand trace on height = [4, 2, 0, 3, 2, 5]:

State: left=0, right=5, left_max=0, right_max=0, total=0

Step 1: h[left]=h[0]=4, h[right]=h[5]=5. 4 <= 5 -> process left.
  h[0]=4 >= left_max=0 -> left_max = 4. left=1.
  total=0

Step 2: h[1]=2, h[5]=5. 2 <= 5 -> process left.
  h[1]=2 < left_max=4 -> total += 4-2=2. left=2.
  total=2

Step 3: h[2]=0, h[5]=5. 0 <= 5 -> process left.
  h[2]=0 < left_max=4 -> total += 4-0=4. left=3.
  total=6

Step 4: h[3]=3, h[5]=5. 3 <= 5 -> process left.
  h[3]=3 < left_max=4 -> total += 4-3=1. left=4.
  total=7

Step 5: h[4]=2, h[5]=5. 2 <= 5 -> process left.
  h[4]=2 < left_max=4 -> total += 4-2=2. left=5.
  total=9

left=5 == right=5. Stop. Return 9. ✓

At step 2, when computing water at position 1, we know left_max=4 and we know height[right]=5 >= 4, so right_max >= 5 >= 4 = left_max. The left side is the binding constraint. The right max could be 5, 100, or a million — it does not change the result. We never need to know it.

Edge cases that actually matter

Each case below and why the code handles it — no separate guard needed for any of them:

• height = [1] or height = [1, 2]: the while loop condition left < right is false immediately, returns 0. Correct — a single bar or two bars cannot form a valley.
• height = [0, 0, 0]: all bars are zero, left_max and right_max stay 0 throughout, total never increases. Returns 0.
• height = [1, 2, 3, 4, 5] (monotone increasing): the right pointer is always taller, so left advances. At each step, height[left] >= left_max (it is strictly increasing), so we keep updating left_max without adding anything. Returns 0.
• height = [5, 4, 3, 2, 1] (monotone decreasing): symmetric — right always advances, right_max updates each time, nothing accumulated. Returns 0.
• height = [3, 0, 3] (equal-height walls): h[left]=3 <= h[right]=3, process left. h[0]=3 >= left_max=0, so left_max=3, advance. Now h[1]=0 <= h[right]=3, h[1]=0 < left_max=3, total += 3. Result is 3. The formula handles ties correctly because the cell is included in its own max — both left_max and right_max include position 0 in the scan respectively.
• height = [2, 0, 2] (symmetrical): both walls equal, water fills the middle cell to min(2,2)-0 = 2. Returns 2.
• All same height, like height = [3, 3, 3, 3]: left_max always equals height[left], so we update max without accumulating. Returns 0 — flat roof, no valley.

Which one to ship

Two pointers for production. The space difference — O(1) vs O(n) — is not the real argument on 20 000-element inputs; the argument is that the two-pointer version is strictly dominated in resource usage and equivalent in speed. The concern is clarity: the two-pointer invariant requires reasoning about what the other side's max must be, and that is not obvious to someone reading the code cold. Prefix/suffix arrays are self-explanatory.

In an interview, I write two pointers. The space win is the expected demonstration that you understand the problem deeply, not just that you can precompute arrays. If the interviewer asks you to walk through why it works, you explain: the shorter side always has its constraint fully known; the taller side's exact max doesn't matter, only that it isn't the bottleneck.

The monotonic stack I would not lead with. It is O(n) time and O(n) space — the same as prefix arrays but harder to read. Its value is that understanding it directly transfers to Largest Rectangle in Histogram (84), which is worth the investment.

Approach comparison

Sibling problems

• Container With Most Water (11): Two pointers at the ends of a height array, move the shorter side inward each step. The decision rule is identical in structure — always process the side that is weaker — but here you are maximising area rather than summing trapped water. Worth doing immediately after this problem; the two-pointer skeleton is almost the same.
• Largest Rectangle in Histogram (84): The mirror image. Instead of filling water between bars, you find the largest rectangle that fits under a skyline. The monotonic stack approach from Approach 3 is exactly the technique that solves 84 efficiently. If the stack variant of this problem confused you, solving 84 next makes both click — the same pattern, opposite direction.
• Trapping Rain Water II (407): The 3-D generalisation. A 2-D grid instead of a 1-D array. The per-cell intuition is the same but the two-pointer trick no longer applies; you need a min-heap (priority queue) to always expand from the shortest boundary cell. Revisit after mastering the 1-D version.
• Sum of Subarray Minimums (907): Uses a monotonic stack in a similar "when does this value stop being the dominant constraint" pattern. Reinforces the stack-based reasoning without the water framing.