Trapping Rain Water

Hard

The problem

Each number in the list is the height of a bar, and every bar is 1 unit wide. After it rains, water collects in the dips between the bars. Return how many units of water are trapped in total.

Example 1
Input: height = [3, 0, 2, 0, 4]
Output: 7
The water level across the middle is 3 (the lower of the two tall bars, 3 and 4). It fills 3 units over position 1, 1 unit over position 2 and 3 units over position 3: 3 + 1 + 3 = 7.
Example 2
Input: height = [2, 0, 2]
Output: 2
The gap between the two walls of height 2 holds 2 units.
Example 3
Input: height = [1, 2, 3]
Output: 0
The bars only go up, so no water stays.

Limits

1 ≤ height.length ≤ 100,000
0 ≤ height[i] ≤ 100,000
Water that would spill off either end is lost

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Water above one bar is limited by the tallest bar on its left and on its right — the smaller of the two.

The idea

Two pointers with leftMax and rightMax. Whichever side has the smaller max is the limiting side: add max − height for that side and move it.

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

Go function shape

func trap(height []int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// Trap: water above a bar = min(tallest bar on its left, tallest bar on its right) - its height.
// Two pointers: the side with the SHORTER wall is the limiting side, so its water level is already known.
func Trap(height []int) int {
	left, right := 0, len(height)-1
	leftMax, rightMax, water := 0, 0, 0
	for left < right {
		if height[left] < height[right] {
			leftMax = max(leftMax, height[left]) // the right wall is at least this tall, so leftMax limits
			water += leftMax - height[left]
			left++
		} else {
			rightMax = max(rightMax, height[right])
			water += rightMax - height[right]
			right--
		}
	}
	return water
}

Read the lesson: Two Pointers