Trapping Rain Water

Problem

Given an elevation map as a 1D array where each value is a bar width 1, compute how much water it can trap after raining. Follow-up: what changes if the map is 2D (a height map)?

Example

[0,1,0,2,1,0,1,3,2,1,2,1]  ->  6

Go Solution

package main

import "fmt"

func trap(height []int) int {
    l, r := 0, len(height)-1
    lMax, rMax, water := 0, 0, 0

    for l < r {
        if height[l] < height[r] {
            if height[l] >= lMax {
                lMax = height[l] // new left wall, no water here
            } else {
                water += lMax - height[l] // trapped above this bar
            }
            l++
        } else {
            if height[r] >= rMax {
                rMax = height[r]
            } else {
                water += rMax - height[r]
            }
            r--
        }
    }
    return water
}

func main() {
    fmt.Println(trap([]int{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1})) // 6
}

How to Solve

1. Water over a bar is set by the shorter of the tallest walls on each side, minus the bar's own height: min(leftMax, rightMax) - height[i].
2. Two pointers from both ends. Move whichever side is currently shorter. That side's answer is fully determined, because the taller opposite wall guarantees the min comes from the side you are moving.
3. Track running maxima. If the current bar is at least as tall as the running max on its side, it becomes the new wall (no water); otherwise it traps max - height.
4. 2D follow-up. Replace the two pointers with a min-heap of boundary cells. Pop the lowest boundary cell, visit its unvisited neighbours, and the water at a neighbour is max(0, boundaryHeight - neighbourHeight); push each neighbour back with max(boundaryHeight, neighbourHeight). The heap always expands inward from the lowest part of the current wall — the 2D generalisation of “move the shorter side.”

Complexity

1D: O(n) time, O(1) space. 2D (heap): O(mn log(mn)) time, O(mn) space.