42. Trapping Rain Water

Q: Why does the two-pointer approach work without seeing the full picture?

When height[left] = height[right] >= height[left]. So the water above the left position is limited by leftMax (the smaller side), which we know exactly. We can safely commit to that water value without moving the right pointer.

hardAsked at Elastic

Compute how much water is trapped between elevation bars after rain. Elastic uses this problem as a hard two-pointer question that tests the ability to reason about running maximums from both directions — the same prefix/suffix scan pattern underlies Elasticsearch's range-scoring and gap-detection in time-series anomaly detection.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Elastic loops.

Glassdoor (2026-Q1)— Trapping Rain Water appears in Elastic hard-difficulty onsite reports, often used to distinguish senior SWE candidates.
Blind (2025-11)— Elastic interview threads note this problem tests prefix-max scanning and two-pointer convergence — both patterns relevant to their time-series stack.

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

Explanation: The elevation map traps 6 units of water.

Example 2

Input

height = [4,2,0,3,2,5]

Output

Explanation: Water fills the valleys between the taller bars.

Approaches

1. Two-pointer O(1) space

Use left and right pointers converging from both ends. Maintain leftMax and rightMax. At each step, process the side with the smaller max — the water above that position is min(leftMax, rightMax) - height[i].

Time: O(n)
Space: O(1)

function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;
  while (left < right) {
    if (height[left] <= height[right]) {
      // Left side is the bottleneck
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left]; // water above left position
      left++;
    } else {
      // Right side is the bottleneck
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

Tradeoff: O(n) time, O(1) space — optimal. The key insight: water at position i is bounded by min(maxLeft, maxRight). By always processing the side with the smaller max, you know exactly how much water that side contributes.

2. Prefix/suffix max arrays

Precompute leftMax[i] = max height from 0 to i, and rightMax[i] = max height from i to n-1. Water at position i = min(leftMax[i], rightMax[i]) - height[i].

Time: O(n)
Space: O(n)

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

Tradeoff: Easier to understand: water at each position is determined by the minimum of the tallest bar to its left and tallest to its right. O(n) space due to two prefix arrays.

Elastic-specific tips

Present the prefix/suffix array approach first to establish correctness, then optimize to two pointers. Elastic interviewers appreciate the explanation: 'The two-pointer approach works because when I process the left side, leftMax is the true maximum to the left of my pointer — and I know the right side has at least rightMax, which is >= leftMax by our if condition, so leftMax is the binding constraint.' This level of invariant reasoning is exactly what senior Elastic engineers demonstrate.

Common mistakes

Computing water as height - min(leftMax, rightMax) instead of min(leftMax, rightMax) - height — this gives the bar height, not the water.
Not updating leftMax/rightMax before computing water — update the max first, then subtract height.
Using strict < instead of <= in the pointer comparison — either works but must be consistent with when you update each max.
Including the boundary bars in the water computation — boundary bars always have 0 water above them (correctly handled by max initialization).

Follow-up questions

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

Container With Most Water (LC 11) — find two bars enclosing maximum area (a simpler two-pointer problem).
Largest Rectangle in Histogram (LC 84) — use a monotonic stack to find the largest rectangle.
How would you compute trapped water in a 2D grid (Volume of water in a 3D terrain)? (LC 407 — uses a min-heap).

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 the two-pointer approach work without seeing the full picture?

When height[left] <= height[right], we know rightMax >= height[right] >= height[left]. So the water above the left position is limited by leftMax (the smaller side), which we know exactly. We can safely commit to that water value without moving the right pointer.

Can a bar's water contribution ever be negative?

No — water = min(leftMax, rightMax) - height[i]. Since leftMax >= height[i] and rightMax >= height[i] by construction, the difference is always >= 0.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →