Problem

Trapping Rain Water

LeetCode #42Hard

Water held between bars of varying heights

Given an elevation map of bar heights, compute how many units of water can be trapped between the bars after rain.

Asked atAmazonGoogleGoldman Sachs

Brute force · scan both sides per column

time O(n²)space O(1)

step 1 / 81

Brute force · scan both sides per column

Better · precompute maxL[] and maxR[] arrays

Optimized · two pointers, O(1) space

[0][1][2][3][4][5][6]

Brute force · scan both sides per column


▸
1given h[]
2total ← 0
3for i ← 0 to n − 1:
4    maxL ← max(h[0..i])
5    maxR ← max(h[i..n − 1])
6    cap = min(maxL, maxR)
7    total += max(0, cap − h[i])
8return total

state

Imagine rain falling on these bars. Where does the water collect? Water can only sit above a column if there are TALLER bars on BOTH sides to hold it.

Tracing pointers...

warming up the animation