Trapping Rain Water

Difficulty: Hard · Topic: Arrays & strings

Given non-negative bar heights, compute how many units of water are trapped between them after raining. Water above index i is bounded by the tallest bar to its left and to its right: min(maxLeft, maxRight) - height[i].

Examples

trap([0,1,0,2,1,0,1,3,2,1,2,1])
→ 6

The classic skyline traps 6 units.

trap([4,2,0,3,2,5])
→ 9

Target complexity: time O(n), space O(1)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.