Skip to main content

98. Trapping Rain Water

hardAsked at Datadog

Compute how much water gets trapped between bars. Datadog uses this for the two-pointer greedy proof — same shape as bounded peak-valley estimation in a streaming metric series.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite hard — two-pointer or stack.
  • Blind (2025-11)— Recurring at Datadog.

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 i, water = min(leftMax[i], rightMax[i]) - height[i].

Time
O(n)
Space
O(n)
// Two passes for left-max and right-max arrays; final pass for water.

Tradeoff: O(n) extra. Datadog accepts; two-pointer is leaner.

2. Two-pointer greedy (optimal)

Two pointers + running leftMax / rightMax. Always process the SHORTER side: water at that side = leftMax/rightMax - height.

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

Tradeoff: O(1) extra space. Datadog-canonical: same proof pattern as Container With Most Water.

Datadog-specific tips

Datadog grades on the WHY of two-pointer. The key insight: at the SHORTER side, the water level is bounded by leftMax/rightMax — the other side doesn't matter because it's taller. Articulate this proof BEFORE coding.

Common mistakes

  • Updating leftMax/rightMax in the wrong order — must check first, then add water.
  • Moving the taller pointer — provably suboptimal.
  • Using a monotonic stack approach when two-pointer is asked — works but uses O(n) memory.

Follow-up questions

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

  • Container With Most Water (LC 11) — related two-pointer.
  • Trapping Rain Water II (LC 407) — 2D variant, min-heap.
  • Datadog-style: bounded valley estimation over a metric stream.

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?

Water at the shorter side is capped by its leftMax/rightMax — we know this WITHOUT seeing the other side, because the other side is taller (bound from above).

Could you use a monotonic stack?

Yes — process bars left to right; the stack holds decreasing heights. Same O(n) but O(n) extra memory.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →