Skip to main content

88. Trapping Rain Water

hardAsked at Salesforce

Compute how much rainwater can be trapped between bars. Salesforce uses this as a two-pointer/precomputed-max stress test — they use the same pattern in their forecast capacity buffers.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses similar two-pointer reasoning in their forecast buffer.
  • Blind (2025-12)— Recurring on Salesforce L5+ onsites.

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. Prefix max + suffix max

For each i, water = min(prefixMax[i], suffixMax[i]) - height[i].

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

Tradeoff: Clear but O(n) space. Salesforce will push for two-pointer O(1).

2. Two pointers with running maxes

l/r pointers. Track leftMax, rightMax. The side with smaller max determines the water level — process that side.

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

Tradeoff: O(1) space. The invariant: the side with smaller height is the limiting side, so water level there equals leftMax or rightMax.

Salesforce-specific tips

Salesforce uses similar two-pointer reasoning in their forecast buffer (capacity-vs-demand calculations). They specifically grade on whether you can ARGUE the correctness of the two-pointer approach — why is the smaller side safe to process? Bonus signal: walk through the invariant explicitly.

Common mistakes

  • Computing water at each i as height[i] - min(left, right) — sign error.
  • Confusing leftMax and rightMax across iterations.
  • Using O(n) prefix/suffix arrays when O(1) two-pointer is achievable.

Follow-up questions

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

  • Container With Most Water (LC 11) — similar two-pointer but different objective.
  • Trapping Rain Water II (LC 407) — 2D, heap-based.
  • Largest Rectangle in Histogram (LC 84).

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 process the smaller side?

Because the water level at the smaller side is bounded by the smaller max. We know everything to its inside has higher walls on the OTHER side, so the limiting wall is on the current (smaller) side.

Why update leftMax/rightMax before adding to total?

Because the water level at position i is at least the running max so far on its side. The order ensures we use the correct level for computation.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →