Skip to main content

24. Trapping Rain Water

hardAsked at Adobe

Given an elevation map, compute how much water it can trap after raining. Adobe uses this hard problem to test whether candidates can derive the two-pointer O(n) insight from first principles — the same "what constrains this position" reasoning appears in histogram-based image segmentation and raster-scan compression.

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

Source citations

Public interview reports confirming this problem appears in Adobe loops.

  • Glassdoor (2026-01)— Adobe SDE-II and senior SDE onsites consistently feature trapping rain water as a hard-tier question.
  • Blind (2025-12)— Adobe candidates report this as the most common hard problem across multiple interview batches.

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

Example 2

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

Approaches

1. Precompute left-max and right-max arrays

For each index, precompute the max height to its left and right. Water at index i = max(0, min(leftMax[i], rightMax[i]) - height[i]).

Time
O(n)
Space
O(n)
function trap(height) {
  const n = height.length;
  const leftMax = Array(n), rightMax = 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 water = 0;
  for (let i = 0; i < n; i++) water += Math.min(leftMax[i], rightMax[i]) - height[i];
  return water;
}

Tradeoff: O(n) time, O(n) space. Correct and easy to derive. Adobe will ask for the O(1) space two-pointer version as a follow-up.

2. Two-pointer O(1) space

Use two pointers l and r starting at both ends. Maintain leftMax and rightMax as running maximums. At each step, process the side with the smaller max: if leftMax <= rightMax, water at l = leftMax - height[l], advance l inward. Otherwise, water at r = rightMax - height[r], advance r inward. The weaker side is always bounded by the stronger side.

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

Tradeoff: O(n) time, O(1) space. The invariant: when processing l, we know rightMax >= height[r] >= leftMax, so the water at l is determined entirely by leftMax (the weaker boundary). Adobe interviewers reward candidates who can articulate this invariant clearly.

Adobe-specific tips

Adobe interviewers grade this problem on the quality of your reasoning about the two-pointer invariant — not just producing the code. Explain why the weaker-side pointer is safe to process: 'Since leftMax <= rightMax, even if there's a taller bar to the right that we haven't seen, the water at l is still determined by leftMax.' Also be ready for the 3D version (Trapping Rain Water II, LC 407) using a min-heap.

Common mistakes

  • Processing the pointer with the greater max instead of the lesser — this breaks the invariant.
  • Off-by-one: not updating leftMax/rightMax before computing water — you must update the max before using it.
  • Using height[l] < height[r] (strict) vs. <= — both work but <= is more natural for the boundary case.

Follow-up questions

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

  • Trapping Rain Water II (LC 407): 3D version with a min-heap/BFS.
  • How would you compute the answer if the elevation array doesn't fit in memory?
  • What is the minimum number of bars you can remove to make the trapped water zero?

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 processing the weaker side work?

When leftMax <= rightMax, we know there exists a bar on the right at least as tall as leftMax (rightMax itself). So the water at l is fully determined by leftMax — it can't be constrained by any unknown bar on the right because none of them will be shorter than rightMax >= leftMax.

Is a stack-based approach also valid?

Yes — maintain a monotonic decreasing stack of indices. When a bar taller than the stack top is found, pop and compute water for the bounded region. O(n) time, O(n) space. Useful for extensions but the two-pointer is preferred at Adobe for its O(1) space.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →