Skip to main content

20. Trapping Rain Water

hardAsked at Brex

Calculate how much water can be trapped between elevation bars — a two-pointer / stack classic that Brex uses to evaluate array reasoning under tight complexity constraints.

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

Example 2

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

Approaches

1. Precompute left/right max arrays

For each index store the max height to its left and right; water at index i is min(leftMax[i], rightMax[i]) - height[i].

Time
O(n)
Space
O(n)
const n = height.length, leftMax = [], 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:

2. Two pointers O(1) space

Maintain left and right pointers plus running maxL and maxR. Move the pointer on the shorter side inward, accumulating water based on the local max minus current height.

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

Tradeoff:

Brex-specific tips

Brex asks about fintech infrastructure, multi-currency handling, and spend management algorithms. Expect LeetCode-style DSA focused on hash maps, sorting, and dynamic programming.

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 Brex interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →