Pattern Guide
Trapping Rain Water
"Water trapped between heights. Two pointers, stack, 2D BFS variants."
Trapping rain water: given heights, compute water trapped above each bar. 1D: water at position i = min(maxLeft[i], maxRight[i]) - height[i]. O(n) two-pointer: maintain l_max and r_max, process from the lower side. Stack-based: process bars as right boundaries, pop when taller bar found, compute trapped water. 2D variant: BFS from border, use min-heap to find lowest boundary.
Problems you can solve with this pattern
4 problems · click any to start solving
function trap(height) {
let l = 0, r = height.length - 1;
let l_max = 0, r_max = 0, water = 0;
while (l < r) {
if (height[l] < height[r]) {
if (height[l] >= l_max) l_max = height[l];
else water += l_max - height[l];
l++;
} else {
if (height[r] >= r_max) r_max = height[r];
else water += r_max - height[r];
r--;
}
}
return water;
}1D two-pointer: l=0, r=n-1, l_max=0, r_max=0. If height[l] < height[r]: if height[l] >= l_max → l_max = height[l]; else add l_max - height[l] to result; advance l. Symmetric for right. Logic: the lower side determines water level at that position. 2D variant: BFS with min-heap from all border cells, process lowest cell first, water = max(0, current_boundary - height[cell]).
function trap(height) {
let l = 0, r = height.length - 1;
let l_max = 0, r_max = 0, water = 0;
while (l < r) {
if (height[l] < height[r]) {
if (height[l] >= l_max) l_max = height[l];
else water += l_max - height[l];
l++;
} else {
if (height[r] >= r_max) r_max = height[r];
else water += r_max - height[r];
r--;
}
}
return water;
}- Two-pointer: O(n) O(1) — process from lower boundary
- Stack: O(n) O(n) — useful for variations (like how many units per level)
- Prefix arrays: O(n) O(n) — precompute leftMax[i] and rightMax[i]
Key insight for two-pointer: When height[l] < height[r], the water at l is determined by l_max (the left boundary limits, not the right). We don't need to know the actual right boundary — we know it's at least height[r] > height[l].
2D rain water: BFS from border using min-heap ensures we always process the lowest boundary first. Water can only be as high as the lowest point on its "wall" to the outside.