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

[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

line 1Imagine 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.

Traversing nodes...

warming up the animation