Skip to main content

25. Trapping Rain Water

hardAsked at ServiceNow

Calculate the total water trapped between elevation bars after rain using two-pointer or stack approaches. ServiceNow asks this hard classic to test multi-pointer reasoning under constraints — the capacity-calculation pattern maps to buffer-management logic in their event ingestion queues.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • LeetCode Discuss (2025)— Reported as a hard coding round question at ServiceNow SDE-II onsite.
  • Glassdoor (2026)— Mentioned in ServiceNow engineering interview prep discussions.

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. Each position traps water equal to min(maxLeft, maxRight) - height[i] if that is positive.

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

Explanation: Bars at positions 2,4,5 trap 1 unit each; bars at positions 6,9 trap 1 unit each; positions 7+ fill accordingly.

Example 2

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

Approaches

1. Precompute maxLeft and maxRight arrays

Build two prefix arrays: maxLeft[i] = max height to the left including i, maxRight[i] = max height to the right including i. Water at each bar = max(0, min(maxLeft[i], maxRight[i]) - height[i]).

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

Tradeoff: Clean and easy to reason about, but uses O(n) extra space. The two-pointer approach reduces space to O(1).

2. Two-pointer O(1) space

Use left and right pointers advancing inward. Maintain maxLeft and maxRight running maxima. Whichever side has the smaller maximum determines water at that pointer's position, because the taller side is guaranteed to provide a wall on the other side.

Time
O(n)
Space
O(1)
function trap(height) {
  let left = 0, right = height.length - 1;
  let maxLeft = 0, maxRight = 0;
  let water = 0;

  while (left < right) {
    if (height[left] <= height[right]) {
      // left side is the bottleneck
      if (height[left] >= maxLeft) {
        maxLeft = height[left];
      } else {
        water += maxLeft - height[left];
      }
      left++;
    } else {
      // right side is the bottleneck
      if (height[right] >= maxRight) {
        maxRight = height[right];
      } else {
        water += maxRight - height[right];
      }
      right--;
    }
  }
  return water;
}

Tradeoff: Optimal O(n) time, O(1) space. The key invariant: when height[left] <= height[right], we know the right boundary is at least height[right] >= maxLeft's effective wall, so maxLeft alone determines water at left.

ServiceNow-specific tips

ServiceNow interviewers want you to clearly articulate the two-pointer invariant before coding: 'the side with the smaller current maximum determines the bottleneck, because we are guaranteed the opposite side provides an equal or taller wall.' Candidates who jump to code without stating this usually make errors on the inner update logic. Bonus signal: frame the problem as buffer-capacity management in their event ingestion pipeline.

Common mistakes

  • Advancing the wrong pointer — must advance the pointer on the side with the smaller maximum, not the smaller current height.
  • Updating maxLeft/maxRight AFTER computing water — must update first, or you compute negative water at a new-high bar.
  • Using height[left] < height[right] strictly — the <= vs < choice does not affect correctness but confuses candidates who don't see why.

Follow-up questions

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

  • Container with most water (LC 11) — related two-pointer but maximizes area, not trapped water.
  • Trapping rain water II: 3D elevation map — use a min-heap BFS from the border.
  • Largest rectangle in histogram (LC 84) — monotonic stack approach that complements this problem.

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 does the two-pointer approach work without knowing the full right/left arrays?

When height[left] <= height[right], the right pointer is at a position that guarantees height[right] >= maxLeft (or will be by the time left catches up). So maxLeft is the definitive bottleneck for the left pointer's water calculation. The symmetric argument applies when height[right] < height[left].

Does it matter which side I start on when heights are equal?

No — when heights are equal, either pointer can advance; both give the same water calculation. The <= vs < convention just picks left consistently.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →