---
title: "Trapping Rain Water (LeetCode #42)"
description: "Build both boundary arrays, then collapse them into two running maxima that settle one column per move"
source: https://vizlearn.app/algorithms/leetcode/trapping-rain-water
---

# Trapping Rain Water (LeetCode #42)

Trapping Rain Water asks how much water remains between elevation bars after rain. Each column can hold water only up to its shorter boundary: the tallest bar seen on its left or right. The interesting part is proving when those two boundaries are known, then adding every column's non-negative depth.

## How trapping rain water works

For an index `i`, let `left_max[i]` be the tallest bar from the start through `i`, and let `right_max[i]` be the tallest bar from `i` through the end. The water above that column is:

`min(left_max[i], right_max[i]) - height[i]`

The current bar is included in both maxima, so this value cannot be negative. A taller wall on only one side is not enough: water spills over the shorter boundary.

The Prefix Max approach makes the proof literal. It builds both arrays, then applies the formula to every column. This takes linear time and linear extra space.

The Two Pointers approach keeps only four values: `left`, `right`, `left_max`, and `right_max`.

### Why the smaller side is final

**Settle the side with the smaller running maximum.** Suppose `left_max <= right_max`.

The scan has already seen a bar on the right whose height is `right_max`. That known wall is at least as tall as `left_max`, so the current left column is enclosed up to `left_max`. Nothing hidden between the pointers can undo that fact: another bar may raise the right wall or become an interior pillar, but it cannot remove the wall already seen. Water also cannot rise above `left_max`, because it would spill over the left boundary.

So the left column's final depth is `left_max - height[left]`. Settle it and move `left` inward. When `right_max < left_max`, the same argument works from the right. Each move permanently settles one column.

## Trapping rain water step by step

The default animation uses `height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]` and the Two Pointers approach.

1. Start at columns 0 and 11. Their running maxima are 0 and 1, so settle the left column with depth 0.
2. Columns 1 and 2 are also settled from the left. Column 2 receives `1 - 0 = 1` unit.
3. At column 3, `left_max` rises to 2 while `right_max` is still 1. The right side is now the smaller boundary, so column 11 settles with depth 0.
4. Column 10 raises `right_max` to 2. With equal boundaries, the trace settles from the left: columns 3, 4, 5, and 6 add 0, 1, 2, and 1 units. The running total reaches 5.
5. Column 7 raises `left_max` to 3, making the right boundary smaller again. Columns 10, 9, and 8 add 0, 1, and 0 units.
6. Only column 7 remains. Equal maxima make the left branch settle it with depth 0. The final total is 6.

Switch to Prefix Max to inspect the same input from another angle. Its left rail becomes `[0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]`; its right rail becomes `[3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]`. Applying the formula produces depths `[0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 0]`, which also sum to 6.

## Time and space complexity

| Approach                            |  Time | Extra space | What it stores                      |
| ----------------------------------- | ----: | ----------: | ----------------------------------- |
| Re-scan both sides for every column | O(n²) |        O(1) | No saved boundaries                 |
| Prefix Max                          |  O(n) |        O(n) | Two arrays of boundary maxima       |
| Two Pointers                        |  O(n) |        O(1) | Two pointers and two running maxima |

Both animated approaches do constant work per column: Prefix Max makes three linear passes, and Two Pointers does constant work for each column it retires. The input editor is capped at 14 bars so the full state stays legible; that is a display limit, not an algorithmic one.

This proof shape transfers to **Container With Most Water**: compare two known boundaries, then move the smaller one because the larger boundary cannot rescue it. The details differ there—it uses the current endpoint heights, not running maxima. Prefix maxima are also a general preprocessing pattern when many later queries need the best boundary seen from each direction.

## Edge cases

- Fewer than three bars cannot enclose water.
- An empty map, flat plateau, or monotone slope traps zero water.
- Equal running maxima are safe: this implementation settles the left side on a tie.
- Zero-height bars are ordinary columns, not missing data. Deep basins can hold several units above one index.
- The first and last columns never hold water because each lacks a wall on one side.

## Common mistakes

- Using `max(left_max, right_max)` instead of `min(...)` invents water above the shorter wall.
- Comparing only `height[left]` and `height[right]` while computing depth from stale maxima mixes two different invariants.
- Moving a pointer before recording the current column skips that column or charges its water to the wrong index.
- Forgetting to update the running maximum before subtracting can produce a negative depth.
- Treating equal maxima as a special deadlock can stall the loop. A consistent tie rule is enough.