Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
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
step 1 / 81
1
2
3
4
2
4
1
3
1
[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
  • n7

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.