Skip to main content

25. Trapping Rain Water

hardAsked at Klarna

Compute how much rain water can be trapped between bars of varying heights.

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 can be trapped after raining.

Constraints

  • 1 <= height.length <= 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. Per-column max scan

For each column, find the max bar to its left and right, then the trapped water is min(maxL, maxR) - height[i].

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

Tradeoff:

2. Two-pointer with running maxima

Walk pointers inward from both ends, tracking the running max on each side. The shorter wall determines the trapped depth at the current column, so always advance the shorter side.

Time
O(n)
Space
O(1)
function trap(h) {
  let l = 0, r = h.length - 1;
  let maxL = 0, maxR = 0, total = 0;
  while (l < r) {
    if (h[l] < h[r]) {
      if (h[l] >= maxL) maxL = h[l];
      else total += maxL - h[l];
      l++;
    } else {
      if (h[r] >= maxR) maxR = h[r];
      else total += maxR - h[r];
      r--;
    }
  }
  return total;
}

Tradeoff:

Klarna-specific tips

Klarna risk-feature engineers map this 'shorter wall bounds the depth' insight to how short-term risk windows bound the BNPL credit exposure on a customer's installment stream; expect a follow-up tying the two-pointer proof back to the underlying invariant.

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

Practice these live with InterviewChamp.AI →