042. Trapping Rain Water

Quick Identifier

Topic: two-pointers
Pattern: two pointers with running side maxima
Difficulty: Hard
Companies: Amazon, Google, Meta, Bloomberg, Microsoft
Frequency: Very High
LeetCode: 42
Hint: Water over a bar is limited by the shorter boundary. Finalize the side whose boundary is known.

Quick Sights

Time Complexity: O(n) - one inward scan.
Space Complexity: O(1) - running maxima replace prefix/suffix arrays.
Core Mechanism: Maintain leftMax and rightMax. Process the side with smaller current height because its opposite boundary is already sufficient.

Concept Explanation

For each index, trapped water is min(maxLeft, maxRight) - height[i]. Prefix/suffix arrays make this obvious, but two pointers compress those arrays into running maxima.

When height[left] < height[right], the right side can already serve as a boundary for left, so the left position can be finalized using leftMax. Symmetrically, process the right side when it is smaller.

Diagram

This diagram shows the pointer decisions and the step-by-step algorithm flow.

Loading diagram…

Study Pattern (SDE3+)

0-3 min: Name the pointer shape, then state the invariant and discard rule before coding.
Implementation pass: Keep pointer movement explicit; every branch must return, record an answer, or move at least one pointer.
5 min extension: Explain how the solution changes for immutable input, streaming input, many duplicate values, or many repeated queries.

Approaches

Naive scanning is O(n^2). Prefix/suffix max arrays are O(n) space. Two pointers are O(n) time and O(1) space.

Optimal Solution

JavaScript

function trap(height) {
	let left = 0;
	let right = height.length - 1;
	let leftMax = 0;
	let rightMax = 0;
	let water = 0;

	while (left < right) {
		if (height[left] < height[right]) {
			if (height[left] >= leftMax) leftMax = height[left];
			else water += leftMax - height[left];
			left++;
		} else {
			if (height[right] >= rightMax) rightMax = height[right];
			else water += rightMax - height[right];
			right--;
		}
	}

	return water;
}

Go

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] {
			if height[left] >= leftMax { leftMax = height[left] } else { water += leftMax - height[left] }
			left++
		} else {
			if height[right] >= rightMax { rightMax = height[right] } else { water += rightMax - height[right] }
			right--
		}
	}
	return water
}