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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Trapping Rain Water and Stacks problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →