Trapping Rain Water

Problem statement

height[i] is the height of a bar of width 1. After rain, water sits in the valleys. Return how many units are trapped.

Example:

Input:

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

Expected output:

6

                    #
            #       # #   #
        #   # #   # # # # # #
    0 1 0 2 1 0 1 3 2 1 2 1

The six units sit in the dips between the bars. The ends hold nothing: there is no wall on the outside.

Practice on LeetCode: Trapping Rain Water

What actually holds the water

Water at index i is not “how tall is this bar.” It is how tall the walls on both sides are.

water[i] = min(tallest to the left, tallest to the right) - height[i]

If that value is negative, the bar sticks up and holds 0. If either side has no taller wall, it also holds 0.

A smaller map makes the formula obvious: [2, 0, 1, 0, 3] traps 5.

          #
    #     #
    #   # #
    # _ # _ #
    2 0 1 0 3

Index 1: min(2, 3) - 0 = 2. Index 2: min(2, 3) - 1 = 1. Index 3: min(2, 3) - 0 = 2.

Why not scan from every index

For each i, walk left for a max and right for a max. That is O(n²). n goes to 2·10^4.

Two arrays fix the time: leftMax[i] and rightMax[i] in a pair of linear passes, then one more pass for the sum. O(n) time, O(n) space.

Two pointers drop the arrays. Same answer, O(1) extra space.

Why the shorter side is enough

Start at both ends. Keep leftMax and rightMax — the tallest bar seen from that end so far.

The water height is limited by the shorter of the two walls. If the bar under the left pointer is shorter than the bar under the right pointer, a wall already exists on the right that is at least height[right]. So the left cell can be settled using leftMax alone. Move left inward. The symmetric case settles the right cell.

That is the same “move the shorter side” skeleton as Container With Most Water. The question is different: units in every valley, not one rectangle.

Golang Solution

Assume n ≥ 1. Seed leftMax and rightMax from the ends. While the pointers have not crossed, process the shorter current bar: raise that side’s max, or add max - height. Then step that pointer inward.

Time: O(n)
Space: O(1)

func trap(height []int) int {
    leftMax := height[0]
    rightMax := height[len(height)-1]

    left, right := 0, len(height)-1

    ans := 0

    for left < right {
        if height[left] < height[right] {
            if height[left] > leftMax {
                leftMax = height[left]
            } else {
                ans += (leftMax - height[left])
            }
            left += 1
        } else {
            if height[right] > rightMax {
                rightMax = height[right]
            } else {
                ans += (rightMax - height[right])
            }
            right -= 1
        }
    }

    return ans
}

The first visit to each end adds 0 (leftMax already equals height[0]). That is correct: the outer bars are walls, not valleys.