Trapping Rain Water

Hard· opposite ends· running max

Problem

An array gives the heights of bars of width 1 in an elevation map. Compute how many units of rainwater are trapped between the bars after it rains.

Examples

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

Output: 6

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

Output: 9

The walls of height 4 and 5 hold water above the lower bars between them.

Constraints

• 1 <= height.length <= 2 * 10^4
• 0 <= height[i] <= 10^5

Hints & approach

Hint 1

Water above bar i is min(tallest bar to the left, tallest bar to the right) - height[i].

Hint 2

Prefix and suffix maximum arrays give an O(n) time, O(n) space answer.

Hint 3

With two pointers, the side with the smaller running maximum already knows its water level.

Approachtry the hints first

Place pointers at both ends and track leftMax and rightMax. If leftMax <= rightMax, the water at left is limited by leftMax (the right side has something at least as tall), so add leftMax - height[left] and move left right after updating leftMax. Otherwise do the mirror step on the right. Each bar is processed once, so it is linear time with constant space.

Time O(n) · Space O(1)

← Previous4Sum DoneBack to Two pointers