RTE logo
← Back to DSA map
Two Pointers

Trapping Rain Water

How much water an elevation map holds after rain.

Hard

Problem

Given n non-negative integers representing an elevation map where each bar is 1 wide, compute how much water it can trap after raining.

  • Water above a bar is limited by the shorter of the tallest walls on its left and right.
  • Bars at the edges cannot hold water.

Examples

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

Approach

Time O(n)Space O(1)
  1. At any index, water = min(leftMax, rightMax) - height[i]: the shorter boundary sets the level.
  2. Start one position at each end and keep track of the tallest wall seen so far on each side.
  3. If height[left] < height[right], the left side is the limiting one: a taller wall is known to exist on the right, so water at left depends only on leftMax. Update leftMax or add leftMax - height[left], then move left inward.
  4. Otherwise do the same from the right. Every bar is visited once, with no extra arrays.

Brute force: For each bar, scan left and right for the tallest walls - a loop inside a loop. Working out all the left and right maximums first gets you down to one pass, but costs two extra arrays.

Common mistakes

  • Moving the taller side instead of the shorter one breaks the thing that makes this work: you only know the other side is at least as tall when you move the shorter one.
  • Adding water before updating the max for a new tallest bar counts negative water.

Step through it

Pick an input and play the algorithm step by step. The highlighted line in the code follows each step, and you can edit the code to experiment.

RAIN
Solution · JS
Bars · L=— R=—
0
0
1
1
0
2
2
3
1
4
0
5
1
6
3
7
2
8
1
9
2
10
1
11
leftMax 0
rightMax 0
added 0
water 0
Left
—
Right
—
LMax
0
RMax
0
Water
0
0 / 0
1×
Execution log
steps appear here…

Solution

The same approach in JavaScript, Python, and Java. Each is a complete program that prints the examples above - JavaScript runs here, so edit it and try your own input.

Edit and run it here

JavaScript solution

Loading...

Output

Run code to see output...

Comments

Sign in to leave a comment. Your name and photo come from Google; nothing else is shared.

Loading comments...