042. Trapping Rain Water

At a Glance

• Topic: two-pointers
• Pattern: Two Pointers (also Dynamic Programming as equivalent formulation)
• Difficulty: Hard
• Companies: Amazon, Google, Meta, Bloomberg, Microsoft
• Frequency: Very High
• LeetCode: 42

Problem (one-liner)

Given non-negative heights of width-1 bars, return how many units of water can be trapped after raining. Water above index index is bounded by min(max height to the left, max height to the right) - height[index].

Recognition Cues

• "Trap rain / water" between bars on a 1D elevation map
• Contribution per index depends on both sides — local maxima form boundaries
• Follow-up: 2D trapping → stack/BFS (different problem)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — for each column, scan outward for left/right max bar — O(n²) time / O(1) space.
• Better (acceptable) — dynamic programming: prefixMax[index], suffixMax[index], water at index is min(prefixMax, suffixMax) - height[index] — O(n) time / O(n) space; easiest to prove correct in whiteboard form.
• Optimal — two pointers from both ends with running maxLeft / maxRight; always advance the shorter side — O(n) time / O(1) space; same volume as DP without auxiliary arrays — preferred when memory matters.

Optimal Solution

Go

func trap(heights []int) int {
	leftPointer, rightPointer := 0, len(heights)-1
	maxLeft, maxRight := 0, 0
	trapped := 0
	for leftPointer < rightPointer {
		if heights[leftPointer] < heights[rightPointer] {
			if heights[leftPointer] >= maxLeft {
				maxLeft = heights[leftPointer]
			} else {
				trapped += maxLeft - heights[leftPointer]
			}
			leftPointer++
		} else {
			// invariant: shorter side is saturated up to the taller boundary on the opposite side
			if heights[rightPointer] >= maxRight {
				maxRight = heights[rightPointer]
			} else {
				trapped += maxRight - heights[rightPointer]
			}
			rightPointer--
		}
	}
	return trapped
}

JavaScript

function trap(heights) {
	let leftPointer = 0;
	let rightPointer = heights.length - 1;
	let maxLeft = 0;
	let maxRight = 0;
	let trapped = 0;
	while (leftPointer < rightPointer) {
		if (heights[leftPointer] < heights[rightPointer]) {
			if (heights[leftPointer] >= maxLeft) {
				maxLeft = heights[leftPointer];
			} else {
				trapped += maxLeft - heights[leftPointer];
			}
			leftPointer++;
		} else {
			if (heights[rightPointer] >= maxRight) {
				maxRight = heights[rightPointer];
			} else {
				trapped += maxRight - heights[rightPointer];
			}
			rightPointer--;
		}
	}
	return trapped;
}

Walkthrough

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

Invariant: the shorter of heights[leftPointer] and heights[rightPointer] is safe to finalize because the taller side guarantees a boundary at least that tall.

Edge Cases

• Empty array → 0
• Strictly increasing / decreasing → 0 trapped
• Plateau ([3,3,3]) → 0
• Single valley ([5,0,5]) → 5
• Large flat zero run in middle

Pitfalls

• Using only min(prefixMax, suffixMax) without the two-pointer ordering proof — correct DP works; two-pointer needs the "process shorter side" rule
• Off-by-one when pointers meet (no double-count center)
• Integer overflow if heights were huge (not an issue on LeetCode int)

Similar Problems

• 11. Container With Most Water — two pointers on bounds; area not volume (stepping-stone on inward scan).
• 15. 3Sum — same “sort / scan with two ends” interview muscle (Medium).
• 84. Largest Rectangle in Histogram — histogram bars; monotonic-stack Hard sibling.

Variants

• 2D trapping — priority-queue boundary expansion or DFS from ocean (Hard).
• Query range [left, right] on static array — RMQ + formula per index, or segment tree.
• Stream of heights — need different structure (only partial stats possible).

Mind-Map Tags

#two-pointers #rain-water #invariant #histogram #O1-space #two-pass-alternative