Skip to main content

42. Trapping Rain Water

hard

Given an elevation map, compute how much rainwater it can trap. Two beautiful solutions — a monotonic decreasing stack that fills basin-by-basin, and a two-pointer sweep with O(1) space.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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

Examples

Example 1

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

Explanation: The elevation map (drawn from the array) traps 6 units of rain water.

Example 2

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Per-index formula: water at i = min(maxLeft[i], maxRight[i]) - height[i]. Precompute both with two passes — that's the O(n) time, O(n) space DP.

Hint 2

Two-pointer optimization: walk l from the left, r from the right; whichever side has the smaller current height is the bound — move that pointer inward and accumulate water.

Hint 3

Stack approach: keep a monotonic decreasing stack of indices. When you see a taller bar, pop the trough and compute the basin: width * (min(left, right) - troughHeight).

Hint 4

All three give the same answer — the two-pointer is the cleanest interview answer.

Solution approach

Reveal approach

Monotonic decreasing stack of indices (by height). Iterate i from 0 to n-1. While the stack is non-empty and height[i] > height[stack.top()], pop the trough index t. If the stack is now empty, there's no left wall — break. Otherwise let l = stack.top() (left wall), compute width = i - l - 1, boundedHeight = min(height[i], height[l]) - height[t], and add width * boundedHeight to the answer. Push i. Each index is pushed and popped at most once: O(n) time, O(n) space. Two-pointer alternative (O(1) space): l = 0, r = n-1, leftMax = rightMax = 0. While l < r: if height[l] < height[r], increment leftMax if needed, else add leftMax - height[l] to ans, then l++. Symmetric on the right. The shorter side always bounds the current cell's water.

Complexity

Time
O(n)
Space
O(n) stack, O(1) two-pointer

Related patterns

  • stack
  • monotonic-stack
  • two-pointers
  • dynamic-programming

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft
  • Apple
  • Bloomberg

More Stacks practice problems

See all Stacks problems →