Skip to main content

88. Trapping Rain Water

hardAsked at Plaid

Compute how much water can be trapped between vertical bars. Plaid asks this as a two-pointer + running-max problem — the same shape they use to compute the cumulative un-allocated liquidity across a fluctuating balance series.

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

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid SWE III onsite — liquidity-window variant.
  • Blind (2026)— Plaid backend platform OA.

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 max-left and max-right arrays

Build leftMax[i] = max of height[0..i] and rightMax[i] = max of height[i..n-1]. Water at i = min(leftMax, rightMax) - height[i].

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

Tradeoff: Linear time, O(n) space. Clear and easy to debug.

2. Two pointers from both ends

Move the shorter side inward. Track maxLeft and maxRight as you go. Water at the shorter side is maxSide - height[ptr].

Time
O(n)
Space
O(1)
function trap(h) {
  let lo = 0, hi = h.length - 1, ml = 0, mr = 0, total = 0;
  while (lo < hi) {
    if (h[lo] < h[hi]) {
      ml = Math.max(ml, h[lo]);
      total += ml - h[lo];
      lo++;
    } else {
      mr = Math.max(mr, h[hi]);
      total += mr - h[hi];
      hi--;
    }
  }
  return total;
}

Tradeoff: O(1) space. The 'move shorter side' invariant means we always know the bottleneck on the moving side — same logic as Container With Most Water.

Plaid-specific tips

Plaid grades this on whether you spot the two-pointer optimization. Bonus signal: prove the 'move shorter' invariant — if h[lo] < h[hi], then on the lo side, ml is the only relevant cap (we know mr >= h[hi] > h[lo] >= ml, so min(ml, mr) = ml). Connect to liquidity-window analysis.

Common mistakes

  • Forgetting that water at i is min of max-left and max-right (using max instead of min).
  • Computing maxes inclusively or exclusively inconsistently.
  • Using the two-pointer version without understanding why moving the shorter side is correct.

Follow-up questions

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

  • Trapping rain water II (LC 407) — 2D heightmap, harder (heap).
  • Maximum capacity between two walls (LC 11).
  • Streaming version — maintain trapped water as bars arrive.

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 move the shorter side?

On the shorter side, the height is bounded by the smaller of the two side maxes. We know the larger max is >= the shorter side's height, so we can safely use the shorter side's max as the cap.

Three-pointer or stack approach?

Both work. Stack-based is great for 'puddle-by-puddle' enumeration; two-pointer is great for total volume. Plaid grades on either.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →