Skip to main content
Monotonic Stack

Trapping Rain Water

Water above each bar = min(tallest bar to its left, tallest bar to its right) − its own height. Precompute left-max and right-max arrays, or use a stack to find bounded regions. Multiple approaches exist.

O(n)
·
O(n)

How It Works

Water trapped above any bar equals min(highest bar to its left, highest bar to its right) minus its own height, clamped at zero. One approach precomputes left-max and right-max prefix arrays and sums the formula per index — O(n) time, O(n) space. The stack approach instead pushes indices while heights decrease; when a taller bar arrives, it pops the valley floor and adds a horizontal slab of water bounded by the popped bar's neighbors.

Both beat the O(n²) brute force of scanning outward from every index. The two-pointer refinement drops the extra arrays entirely: move whichever side has the smaller max inward, accumulating water against the smaller boundary, achieving O(n) time with O(1) space.

Step-by-Step Visualization

Trap rainwater between bars
L
0
0
1
1
0
2
2
3
1
4
0
5
1
6
R
3
7
leftMax0
rightMax0
1/4

Code

Java
static int trap(int[] height) {
  int left = 0, right = height.length - 1;
  int leftMax = 0, rightMax = 0, water = 0;

  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

// Example: trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}) → 6

Tips & Gotchas

1Water at position i = min(maxLeft, maxRight) - height[i]
2Can use two-pointer approach for O(1) space
3Stack approach: push decreasing bars, pop when taller bar arrives

Practice Problems

  • 1Trapping Rain Water
  • 2Container With Most Water
  • 3Trapping Rain Water II
  • 4Pour Water

About the Monotonic Stack Pattern

Keep the stack in sorted order (always increasing or always decreasing). When a new element would break the order, pop elements until the order is restored. Each popped element just found its 'answer' (the element that caused the pop).

Key insight

Monotonic stacks are the power tool here. If you need 'next greater/smaller element' or 'span' queries, a monotonic stack gives O(n) instead of O(n²).

Common Stack Interview Problems

  • Valid Parentheses
  • Next Greater Element
  • Largest Rectangle in Histogram
  • Trapping Rain Water
  • Daily Temperatures
  • Decode String

Frequently Asked Questions

How do the stack and prefix-array approaches differ in what they accumulate?

The prefix-array method computes water column by column, one vertical strip per index. The stack method computes water layer by layer, adding horizontal slabs each time a valley gets bounded on both sides. Both sum to the same total in O(n).

When can I use the two-pointer version safely?

Whenever you only need the total volume. The key invariant is that the side with the smaller running maximum is fully determined by that maximum, so you can settle its water without knowing the other side exactly. If you need per-index water or 2D terrain, use the arrays or a heap-based approach instead.