All problems

Trapping Rain Water

Hard · two pointers

The list height describes a row of bars standing side by side. Every bar is one unit wide, and height[i] is how tall bar i is. Beyond the first and last bar there is nothing, so water that reaches either end of the row runs off and is lost.

After a heavy shower, water collects in the gaps between taller bars. Return the total number of units of water that are left standing on the whole row once the rain stops.

Water also settles on top of the lower bars inside a dip, not only in the gaps between bars, and a bar of height 0 is just an empty column that water can fill.

Examples

Example 1

Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

Output: 6

Three pools form: 1 unit above the 0 between the 1 and the 2, 4 units over the three bars between the 2 and the 3 (1, 2 and 1 units above the bars of height 1, 0 and 1), and 1 unit above the 1 between the two 2s near the end. That is 6 in total.

Example 2

Input: height = [4, 2, 0, 3, 2, 5]

Output: 9

The 4 on the left and the 5 on the right hold a pool: 2 above the 2, 4 above the 0, 1 above the 3 and 2 above the second 2.

Example 3

Input: height = [1, 2, 3]

Output: 0

Every bar is taller than the one before it, so any water would run off the left side.

Constraints