Skip to main content

42. Trapping Rain Water

hardAsked at Microsoft

Trapping Rain Water is the Microsoft hard that separates the two-pointer fluent from the rest. Naive answer is O(n^2). DP with leftMax/rightMax arrays is O(n) time + O(n) space. The two-pointer version is O(n) time + O(1) space — the bonus the interviewer is hoping you reach.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Microsoft loops.

  • Glassdoor (2026-Q1)— Microsoft Azure/Office org senior onsite reports list Trapping Rain Water as a recurring 45-minute hard.
  • Blind (2025-12)— Microsoft L62/L63 interview compilations include Trapping Rain Water with the two-pointer optimization expectation.

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 traps 6 units of rain water.

Example 2

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

Approaches

1. Brute-force (per-index leftMax/rightMax)

For each index i, scan left and right for the maxes. Water[i] = min(leftMax, rightMax) - height[i].

Time
O(n^2)
Space
O(1)
function trap(height) {
  let total = 0;
  for (let i = 0; i < height.length; i++) {
    let lMax = 0, rMax = 0;
    for (let l = 0; l <= i; l++) lMax = Math.max(lMax, height[l]);
    for (let r = i; r < height.length; r++) rMax = Math.max(rMax, height[r]);
    total += Math.min(lMax, rMax) - height[i];
  }
  return total;
}

Tradeoff: Quadratic; mention as the wrong answer. The invariant — water at i is bounded by min(maxLeft, maxRight) — is the right one to keep.

2. DP precompute leftMax and rightMax arrays

Two passes precompute leftMax[i] and rightMax[i]. Third pass sums min(leftMax[i], rightMax[i]) - height[i].

Time
O(n)
Space
O(n)
function trap(height) {
  const n = height.length;
  if (n === 0) return 0;
  const leftMax = new Array(n);
  const rightMax = new Array(n);
  leftMax[0] = height[0];
  for (let i = 1; i < n; i++) leftMax[i] = Math.max(leftMax[i - 1], height[i]);
  rightMax[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) rightMax[i] = Math.max(rightMax[i + 1], height[i]);
  let total = 0;
  for (let i = 0; i < n; i++) total += Math.min(leftMax[i], rightMax[i]) - height[i];
  return total;
}

Tradeoff: Linear time and space. Easier to write than the two-pointer version and Microsoft accepts it; the follow-up is always 'now do it in O(1) space.'

3. Two pointers (optimal O(1) space)

Maintain left and right pointers, leftMax and rightMax. Whichever side has the smaller current height moves inward; the water trapped at that side equals sideMax - sideHeight.

Time
O(n)
Space
O(1)
function trap(height) {
  let l = 0, r = height.length - 1;
  let lMax = 0, rMax = 0;
  let total = 0;
  while (l < r) {
    if (height[l] < height[r]) {
      if (height[l] >= lMax) lMax = height[l];
      else total += lMax - height[l];
      l++;
    } else {
      if (height[r] >= rMax) rMax = height[r];
      else total += rMax - height[r];
      r--;
    }
  }
  return total;
}

Tradeoff: The invariant: if height[l] < height[r], we know rMax >= height[r] > height[l], so the water level at l is determined by lMax alone — no need to know the actual rMax. Same applies symmetrically on the right. This is what makes O(1) space possible.

Microsoft-specific tips

Microsoft is grading whether you can articulate the two-pointer invariant. Memorize: 'if the LEFT bar is shorter, the right side has at least one bar taller, so water at the left is bounded by leftMax only.' Then move left in. That sentence is the entire optimal solution and is worth ~70% of the interview score.

Common mistakes

  • Mixing up which side to advance in the two-pointer version (always advance the SHORTER side).
  • Using strict < instead of <= in the height[l] < height[r] check — works but the equal-heights tiebreak is arbitrary.
  • Off-by-one on rightMax loop when n == 1 — handle the empty/single-element case up front.

Follow-up questions

An interviewer at Microsoft may pivot to one of these next:

  • Trapping Rain Water II (LC 407) — 2D grid, min-heap of the boundary.
  • Container With Most Water (LC 11) — similar two-pointer idea but different objective (max area).
  • Largest Rectangle in Histogram (LC 84) — companion stack problem.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why does moving the shorter side first work?

Because the water level at that side is determined by the smaller of leftMax and rightMax. If left is shorter than right's current height, we already know rightMax > height[l], so leftMax alone bounds the water on the left side.

What if the entire array is monotonically increasing?

Zero water — every position has a leftMax equal to itself, so min - height = 0 everywhere.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Trapping Rain Water and other Microsoft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →