Trapping Rain Water

The problem. Given n non-negative integers height describing an elevation map where every bar has width 1, compute how much water it can trap after raining.

The elevation map 0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1 with rain water shown in blue in the dips between bars: one unit above index 2, one above index 4, two above index 5, one above index 6 and one above index 9, six units in total.

Example

Input:  height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]    Output: 6
Input:  height = [4, 2, 0, 3, 2, 5]                      Output: 9

Think about one column. Water above it rises until it would spill over the lower of the two "walls" around it: the tallest bar anywhere to its left and the tallest bar anywhere to its right.

Water above one column. For index 5 (height 0), the tallest bar on its left has height 2 and the tallest on its right has height 3. The water level is the smaller of the two, 2, so the column holds 2 - 0 = 2 units.

Free account

Keep reading. It's free.

Sign up to read the rest of this lesson: 5 more sections, 3 drawings, 2 dry-run simulators and code in JavaScript, Python, Java and C++.

Still to come

1. Brute force: look both ways from every bar
2. Optimal: a monotonic stack fills the water in layers
3. Best solution: two pointers, O(1) space
Comparing the three approaches
Edge cases to test

Mark completed

Was this helpful?

QueueFirst-in, first-out — the structure behind task scheduling and breadth-first traversal.4 lessons · 5 problems
Linked ListNodes linked one direction by pointers instead of contiguous memory.4 lessons · 12 problems
ArraysContiguous, indexable memory — the foundation almost every other data structure builds on.12 lessons · 16 problems

Trapping Rain Water

Example

Keep reading. It's free.

Keep exploring