practice · hard · from Arrays

Trapping Rain Water

time: O(n)
space: O(1)
tags: arrays · two-pointer

in the wild Terrain reservoirs — given an elevation profile, how much rainwater settles in the valleys?

Two pointers · converging

…

speed step 0 / 0

Problem

Given an array of non-negative integers heights representing the elevation of bars at unit-width positions, compute how much rainwater would be trapped between the bars after it rains.

Examples

heights = [0,1,0,2,1,0,1,3,2,1,2,1] → 6

 3 |         ▓
 2 |     ▓~~~▓~~▓
 1 |  ▓~~▓~~~▓~~▓~~▓~~▓
 0 |__▓__▓__▓▓__▓__▓__
     (each ~ is one unit of trapped water)

heights = [4, 2, 0, 3, 2, 5] → 9
heights = [0] → 0 — single bar can hold no water

Why this is the canonical two-pointer problem

Naïve: for each position i, look left for the tallest bar (max_left[i]) and right for the tallest bar (max_right[i]). The water sitting on top of position i is min(max_left[i], max_right[i]) - heights[i] (clamped to ≥ 0). Sum across all positions.

That's correct but O(n²) if you re-scan each time, or O(n) time + O(n) space if you precompute the two max_* arrays.

The two-pointer solution gets it to O(n) time + O(1) space — but it requires a non-obvious observation: at each step, the shorter side determines the water level, so you can advance that pointer without losing information.

This is the prototypical problem where the right data-structure mental model isn't "what to add" but "what direction to scan from."

Hints

Hint 1 — observe the water level

The amount of water above position i is min(max_left[i], max_right[i]) - heights[i]. Why is it min and not max? Picture pouring water: it spills over the shorter wall on either side.

Hint 2 — collapse the bookkeeping

You don't need both full max_left and max_right arrays at the same time. You only need the smaller of the two — the other one only matters when it would exceed the smaller one.

Maintain a left pointer l and right pointer r. Track max_left (highest seen from the left so far) and max_right (highest seen from the right so far).

At each step, whichever side has the shorter running max is the side where you know the water level. Advance that side; add the trapped water on the way.

Hint 3 — pseudocode

l, r = 0, n-1
max_left = max_right = 0
total = 0
while l < r:
    if heights[l] < heights[r]:
        if heights[l] >= max_left: max_left = heights[l]
        else: total += max_left - heights[l]
        l += 1
    else:
        if heights[r] >= max_right: max_right = heights[r]
        else: total += max_right - heights[r]
        r -= 1
return total

The key invariant: when heights[l] < heights[r], we know the water level at l is at most max_left, regardless of what's to the right — because we know there exists a bar on the right (namely heights[r]) that's at least heights[l]. Symmetric for the other branch.

Solution

def trap(heights: list[int]) -> int:
    if len(heights) < 3:
        return 0
    l, r = 0, len(heights) - 1
    max_left = max_right = 0
    total = 0
    while l < r:
        if heights[l] < heights[r]:
            # right side has a guaranteed wall ≥ heights[l]; bottleneck = max_left
            if heights[l] >= max_left: max_left = heights[l]
            else:                       total += max_left - heights[l]
            l += 1
        else:
            if heights[r] >= max_right: max_right = heights[r]
            else:                        total += max_right - heights[r]
            r -= 1
    return total

cases = [
    ([0,1,0,2,1,0,1,3,2,1,2,1],  6),     # classic example
    ([4, 2, 0, 3, 2, 5],         9),
    ([1, 2, 3, 4, 5],            0),     # monotonic — no valley
    ([5, 4, 3, 2, 1],            0),
    ([],                         0),     # degenerate
    ([1],                        0),
    ([1, 2],                     0),
]
for h, expected in cases:
    got  = trap(h)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} trap({h}) = {got}  (expected {expected})")

function trap(heights) {
  if (heights.length < 3) return 0;
  let l = 0, r = heights.length - 1;
  let maxLeft = 0, maxRight = 0;
  let total = 0;
  while (l < r) {
    if (heights[l] < heights[r]) {
      if (heights[l] >= maxLeft) maxLeft = heights[l];
      else                       total += maxLeft - heights[l];
      l++;
    } else {
      if (heights[r] >= maxRight) maxRight = heights[r];
      else                        total += maxRight - heights[r];
      r--;
    }
  }
  return total;
}

const cases = [
  [[0,1,0,2,1,0,1,3,2,1,2,1],  6],
  [[4, 2, 0, 3, 2, 5],         9],
  [[1, 2, 3, 4, 5],            0],
  [[5, 4, 3, 2, 1],            0],
  [[],                         0],
  [[1],                        0],
  [[1, 2],                     0],
];
for (const [h, expected] of cases) {
  const got = trap(h);
  console.log(`${got === expected ? "✓" : "✗"} trap(${JSON.stringify(h)}) = ${got}  (expected ${expected})`);
}

pub fn trap(heights: &[i32]) -> i32 {
    if heights.len() < 3 { return 0; }
    let mut l = 0;
    let mut r = heights.len() - 1;
    let mut max_left  = 0;
    let mut max_right = 0;
    let mut total     = 0;
    while l < r {
        if heights[l] < heights[r] {
            // right has a wall ≥ heights[l] → bottleneck at l is max_left.
            if heights[l] >= max_left { max_left = heights[l]; }
            else                       { total += max_left - heights[l]; }
            l += 1;
        } else {
            if heights[r] >= max_right { max_right = heights[r]; }
            else                        { total += max_right - heights[r]; }
            r -= 1;
        }
    }
    total
}

fn main() {
    let cases: &[(&[i32], i32)] = &[
        (&[0,1,0,2,1,0,1,3,2,1,2,1],  6),
        (&[4, 2, 0, 3, 2, 5],         9),
        (&[1, 2, 3, 4, 5],            0),
        (&[5, 4, 3, 2, 1],            0),
        (&[],                         0),
        (&[1],                        0),
        (&[1, 2],                     0),
    ];
    for (h, expected) in cases {
        let got  = trap(h);
        let mark = if got == *expected { "✓" } else { "✗" };
        println!("{mark} trap({:?}) = {}  (expected {})", h, got, expected);
    }
}

#include <iostream>
#include <vector>

int trap(const std::vector<int>& heights) {
    if (heights.size() < 3) return 0;
    int l = 0, r = (int)heights.size() - 1;
    int max_left = 0, max_right = 0, total = 0;
    while (l < r) {
        if (heights[l] < heights[r]) {
            if (heights[l] >= max_left) max_left = heights[l];
            else                         total += max_left - heights[l];
            ++l;
        } else {
            if (heights[r] >= max_right) max_right = heights[r];
            else                          total += max_right - heights[r];
            --r;
        }
    }
    return total;
}

int main() {
    struct Case { std::vector<int> h; int expected; };
    std::vector<Case> cases = {
        {{0,1,0,2,1,0,1,3,2,1,2,1},  6},
        {{4, 2, 0, 3, 2, 5},         9},
        {{1, 2, 3, 4, 5},            0},
        {{5, 4, 3, 2, 1},            0},
        {{},                         0},
        {{1},                        0},
        {{1, 2},                     0},
    };
    for (auto& c : cases) {
        int got = trap(c.h);
        std::cout << (got == c.expected ? "✓" : "✗") << " trap({";
        for (size_t i = 0; i < c.h.size(); ++i)
            std::cout << c.h[i] << (i + 1 < c.h.size() ? "," : "");
        std::cout << "}) = " << got << "  (expected " << c.expected << ")\n";
    }
}

#include <stdio.h>

int trap(const int* h, int n) {
    if (n < 3) return 0;
    int l = 0, r = n - 1;
    int max_left = 0, max_right = 0, total = 0;
    while (l < r) {
        if (h[l] < h[r]) {
            if (h[l] >= max_left) max_left = h[l];
            else                  total   += max_left - h[l];
            ++l;
        } else {
            if (h[r] >= max_right) max_right = h[r];
            else                   total    += max_right - h[r];
            --r;
        }
    }
    return total;
}

static void show(const int* h, int n, int expected) {
    int got = trap(h, n);
    printf("%s trap({", got == expected ? "✓" : "✗");
    for (int i = 0; i < n; i++) printf("%d%s", h[i], i + 1 < n ? "," : "");
    printf("}) = %d  (expected %d)\n", got, expected);
}

int main(void) {
    int a[] = {0,1,0,2,1,0,1,3,2,1,2,1}; show(a, 12, 6);
    int b[] = {4, 2, 0, 3, 2, 5};        show(b, 6,  9);
    int c[] = {1, 2, 3, 4, 5};           show(c, 5,  0);
    int d[] = {5, 4, 3, 2, 1};           show(d, 5,  0);
    int e[] = {1};                       show(e, 1,  0);
    int f[] = {1, 2};                    show(f, 2,  0);
    return 0;
}

idle

The cleverness across all five: when heights[l] < heights[r], some bar on the right is at least as tall as heights[l], so when we eventually compute max_right it will be ≥ heights[l]. That means the water level at l is bottlenecked by max_left — full stop. We don't need to know max_right exactly. Same insight, five implementations.

Complexity

Time: O(n) — each pointer crosses the array at most once; total pointer moves = n - 1.
Space: O(1) — just the two pointers and two running maxes.
vs precomputed-arrays approach: The "precompute max_left[] and max_right[]" version is also O(n) time but O(n) space. Two-pointer wins on memory by recognizing you only need the shorter side at any given moment.

In the wild

Two-pointer techniques on arrays show up wherever you're balancing two ends:

Terrain reservoirs. Given a 1D elevation profile (LIDAR slice, map column), how much water settles between hills? Same algorithm, different unit.
Container with most water. Find the two bars that, treated as walls, hold the largest rectangle of water. Same two-pointer move, slightly different objective.
Merge two sorted arrays. Two pointers from each input head, advance the smaller one each step.
Palindrome check. Pointer from each end, walk inward.

Variations

Trap rain water II (2D heightmap). Same problem but on a grid. The two-pointer trick doesn't generalize cleanly; the canonical solution uses a min-heap of border cells (priority by current height). This is one of the places the heap lesson's "always pop the lowest" pattern earns its keep.
Largest rectangle in histogram. Different objective, but the same "running state across the array" mindset. Solved with a stack of pending bars.