two-pointers · Problem 4 of 4

Trapping Rain Water

hard

Amazon

Google

Meta

Goldman Sachs

Apple

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

trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) -> 6
trap([4, 2, 0, 3, 2, 5])                   -> 9
trap([])                                   -> 0

Your solution

input

Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.

Running is free — Submit is what records it. Or press ⌘↩

5 cases, 1 hidden

call	type	expected	result
trap([0,1,0,2,1,0,1,3,2,1,2,1])	standard multi-peak elevation	6	—
trap([4,2,0,3,2,5])	valley elevation	9	—
trap([1,2,3,4,5])	strictly ascending (no trap)	0	—
trap([])	empty elevation	0	—
withheld	hidden	withheld	—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Optimal two-pointer approach requiring a single pass and constant extra space.

Stuck? Hints open one at a time, each giving a little more away.

3 hints left