Trapping rain water

hardTwo pointers target 40 min

Trapping rain water

Not solved yetLeetCode 42. Trapping Rain Water

A row of bars stands on flat ground, side by side with no gaps. Bar i is 1 unit wide and heights[i] units tall; a height of 0 is bare ground. It rains until every spot that can hold water is full. Water cannot pass through a bar, it spreads sideways freely, and any water that reaches either end of the row runs off.

Return the total amount of water left standing on the row, in units, where one unit fills a 1 by 1 square.

Example 1

Inputheights = [3, 0, 2, 0, 4]Output7

The water level is 3, set by the left bar. Water stands 3 deep over position 1, 1 deep over position 2 and 3 deep over position 3: 3 + 1 + 3 = 7.

Example 2

Inputheights = [0, 2, 0, 0, 1]Output2

The right wall is only 1 tall, so water stands 1 deep over positions 2 and 3. Position 0 has no wall on its left, so water there runs off.

Example 3

Inputheights = [1, 2, 3, 2, 1]Output0

A hill holds nothing: all the water runs off both sides.

Constraints

0 ≤ len(heights) ≤ 10⁵
0 ≤ heights[i] ≤ 10⁵

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern