Trapping Rain Water — Monotonic Stack Layered Fill

Problem Statement#

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Constraints:

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

Input:  height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Input:  height = [4,2,0,3,2,5]
Output: 9

Why This Problem Matters#

LeetCode 42 Trapping Rain Water is the most famous monotonic stack hard problem and is asked at Amazon, Google, Meta, Apple, and Microsoft year after year. It admits at least three solutions (precomputed left-max plus right-max arrays, two-pointer, monotonic stack), each illustrating a different paradigm. Recruiters use it to confirm that you can compare solutions on time, space, and conceptual cleanliness.

The monotonic stack solution is the most general and the most extensible — it directly generalizes to Trapping Rain Water II (3D, LeetCode 407 with a heap), to building Largest Rectangle in Histogram intuition, and to many "find boundaries on each side" problems. Mastering this single problem unlocks a tier of FAANG-grade interview readiness.

The Core Insight#

Water sits in a basin formed by a left wall and a right wall. For any column i, the water above it is min(maxLeft, maxRight) minus height[i], capped at 0.

Three approaches:

1. Precompute leftMax and rightMax arrays — O(n) time and O(n) space.
2. Two pointers — O(n) time, O(1) space, exploiting that the smaller side determines the water.
3. Monotonic decreasing stack — fills water layer by layer as we scan, O(n) time and O(n) space.

The stack approach: maintain a stack of indices whose heights are non-increasing from bottom to top. When we see a new bar i with height greater than the stack top, the top is the bottom of a basin whose left wall is the new top after popping (or no wall if the stack becomes empty) and whose right wall is i. Compute the trapped water for that horizontal layer and continue.

This is the same skeleton as Largest Rectangle in Histogram but with a different formula for the contribution per pop.

Visual Dry Run#

height equals [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1].

We iterate i from 0 to n minus 1. Stack stores indices.

Final water equals 6. Matches expected output.

Solution (Optimal)#

from typing import List
 
def trap(height: List[int]) -> int:
    stack = []  # indices with non-increasing heights
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            depth = min(height[left], h) - height[bottom]
            water += width * depth
        stack.append(i)
    return water

function trap(height) {
  const stack = [];
  let water = 0;
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[stack[stack.length - 1]] < height[i]) {
      const bottom = stack.pop();
      if (!stack.length) break;
      const left = stack[stack.length - 1];
      const width = i - left - 1;
      const depth = Math.min(height[left], height[i]) - height[bottom];
      water += width * depth;
    }
    stack.push(i);
  }
  return water;
}

Complexity. Time O(n) — each index is pushed and popped at most once. Space O(n) for the stack.

Common Mistakes#

• Using strict greater-than only when popping. Equal-height bars are not basins, but you must still push to keep the stack monotonic.
• Forgetting to break out of the while loop when the stack becomes empty after popping the bottom — there is no left wall, so no water adds for this layer.
• Confusing the depth formula. The correct formula is min(left height, right height) minus bottom height, not min(left, right).
• Mixing the layered (stack) approach with the two-pointer approach mid-solution.
• Returning the count of pops or the maximum layer instead of the cumulative water.

Interview Tips#

• State all three approaches (precomputed arrays, two pointers, monotonic stack) up front. Pick one based on what the interviewer wants — if they want the cleanest code use two-pointer, if they want the most general approach use the stack.
• Walk through the dry run to make the layered fill concrete, especially the cascade of pops at i = 7 in the example.
• Mention that the stack approach generalizes to Trapping Rain Water II (3D) by replacing the stack with a min-heap.
• Reference Largest Rectangle in Histogram as a sibling problem with the same skeleton but different per-pop formula.
• If asked, derive the time bound: each index pushed once and popped once.

Follow-up Questions#

1. What if the elevation map can change dynamically? Use a segment tree of (max, water) values and recompute affected ranges on update.
2. Trapping Rain Water II (3D)? Use a min-heap seeded with all border cells; expand inward, accumulating water.
3. What if widths are not all 1? Multiply width by per-cell width; use cumulative width arrays.
4. What about negative heights? Treat them as basin floors; the formula still works.
5. How would you parallelize over a giant elevation map? Partition into chunks; compute per-chunk trapped water plus merge boundary regions.

Key Takeaways#

• A monotonic decreasing stack fills water layer by layer in O(n).
• For each pop, the trapped water rectangle has width equal to right-index minus left-index minus 1 and depth equal to min(left height, right height) minus popped height.
• The two-pointer approach gives the same O(n) time with O(1) space; the stack is more general.
• Pattern generalizes to Trapping Rain Water II (heap), Largest Rectangle in Histogram, and many "boundary on each side" problems.
• Time O(n), space O(n) for the stack.
• This is the signature FAANG monotonic stack problem — master it and many derivatives become accessible.