Skip to main content

30. Trapping Rain Water

hardAsked at Tripadvisor

Calculate total water trapped between elevation bars after rainfall — Tripadvisor's geographic elevation team models terrain profiles for outdoor activity recommendations, and this two-pointer DP pattern is a canonical elevation-analysis building block.

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: 6 units of water are trapped in the valleys.

Example 2

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

Approaches

1. Precomputed left/right max arrays (DP)

For each index, water trapped = min(maxLeft[i], maxRight[i]) - height[i]. Precompute maxLeft and maxRight in two passes, then compute trapped water in a third pass.

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

Tradeoff:

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

Use left and right pointers moving inward. At each step, the pointer on the side with the smaller max determines trapped water — process it and advance that pointer. Eliminates the two extra arrays.

Time
O(n)
Space
O(1)
function trap(height) {
  let lo = 0, hi = height.length - 1;
  let maxLeft = 0, maxRight = 0, water = 0;
  while (lo < hi) {
    if (height[lo] <= height[hi]) {
      if (height[lo] >= maxLeft) maxLeft = height[lo];
      else water += maxLeft - height[lo];
      lo++;
    } else {
      if (height[hi] >= maxRight) maxRight = height[hi];
      else water += maxRight - height[hi];
      hi--;
    }
  }
  return water;
}

Tradeoff:

Tripadvisor-specific tips

Tripadvisor interviewers rate this as a barometer problem for senior candidates — if you jump straight to two pointers without first explaining the DP approach, they'll probe whether you understand why it works. Walk through the DP solution first (min of left max, right max), then derive the two-pointer optimization by arguing that once you know which side is the bottleneck you can process it without needing the other side's full array. The correctness argument is the hard part — nail it and you stand out.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →