Skip to main content

42. Trapping Rain Water

hardAsked at HP

HP's physical simulation software for environmental testing — used in product durability labs — models fluid accumulation on irregular surfaces. Trapping Rain Water is the algorithmic abstraction of this problem. HP engineers encounter it in the context of dynamic programming, two-pointer optimization, and reasoning about monotonic stack patterns.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2026-Q1)— HP SWE senior candidates report Trapping Rain Water appearing in final onsite rounds as a demonstration of multi-approach mastery.
  • Blind (2025-10)— HP interview prep discussions list Trapping Rain Water among harder problems expected for senior-level HP engineering roles.

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

Explanation: 6 units of water are trapped between the bars.

Example 2

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

Explanation: 9 units trapped.

Approaches

1. Prefix/suffix max arrays (DP)

Precompute leftMax[i] = max height from 0 to i and rightMax[i] = max height from i to end. Water at i = min(leftMax[i], rightMax[i]) - height[i].

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

Tradeoff: O(n) time, O(n) space. Intuitive and easy to verify. The formula min(leftMax, rightMax) - height[i] directly captures the water level above each bar.

2. Two pointers (O(1) space)

Use two pointers (left, right) and track running maximums. The pointer pointing to the smaller max dictates the water level and can safely be processed.

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

Tradeoff: O(n) time, O(1) space. The space-optimal solution. The key insight: if height[left] ≤ height[right], the left side is the bottleneck — water at left is determined by leftMax regardless of anything to the right (which is at least as tall).

HP-specific tips

HP interviewers expect you to know at least two approaches. Present the DP approach first for clarity, then optimize to O(1) space with two pointers. The two-pointer insight — 'process the side with the smaller max because the taller side guarantees the water level is determined by the smaller side' — should be stated explicitly. Trace through the [0,1,0,2,...] example step by step with two pointers to demonstrate correctness.

Common mistakes

  • Summing max(0, min(leftMax, rightMax) - height[i]) — the Math.max(0,...) is not needed if the arrays are computed correctly (they are always ≥ height[i]).
  • In two-pointer: checking height[left] < height[right] strictly — ties can go either way but must be consistent.
  • Updating leftMax/rightMax before computing water — update first (to reflect current height if it's a new max), then accumulate water.
  • Not understanding why the two-pointer result is correct — be prepared to explain the invariant, not just the code.

Follow-up questions

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

  • Solve with a monotonic stack — useful for related problems like Largest Rectangle in Histogram.
  • What if the elevation map wraps around (circular)? How does water accumulate?
  • 3D Trapping Rain Water (LC 407) — extend to a 2D height map.

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 is it safe to process the smaller-max side first in two-pointer?

If height[left] ≤ height[right], the right side is at least as tall. So the water level at left is fully determined by leftMax — no matter what lies between left and right, water can't spill past the right boundary.

What does leftMax represent in the two-pointer approach?

leftMax is the maximum height seen so far from the left pointer's position to the left boundary. It's the 'wall' constraining water on the left side.

Can the water accumulation be negative for any bar?

No — min(leftMax, rightMax) is always ≥ height[i] by definition of leftMax and rightMax. The subtraction is always ≥ 0.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →