Skip to main content

42. Trapping Rain Water

hardAsked at HubSpot

HubSpot asks Trapping Rain Water to evaluate your ability to reason about bounded quantities — how much water a cell can hold is determined by the minimum of the tallest bars on its left and right — a constraint-propagation mindset they value in their data pipeline engineers.

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

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

  • Glassdoor (2026-Q1)— HubSpot SWE onsite reports include Trapping Rain Water as an advanced hard problem in senior engineering interviews.
  • Blind (2025-09)— Multiple HubSpot interview threads cite Trapping Rain Water as a hard two-pointer problem for senior SWE candidates.

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: The elevation map traps 6 units of water: between bars at positions 1-3, 4-7, etc.

Example 2

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

Explanation: Traps 9 units total — each position holds min(maxLeft, maxRight) - height[i] units.

Approaches

1. Prefix/suffix max arrays

Precompute maxLeft[i] and maxRight[i] — the tallest bar to the left and right of each position. Water at i = min(maxLeft[i], maxRight[i]) - height[i].

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

Tradeoff: Clear and easy to verify. O(n) time and O(n) extra space. A good first approach to explain the formula, before optimizing to O(1) space with two pointers.

2. Two-pointer (O(1) space)

Move two pointers from both ends inward. The pointer pointing to the shorter bar moves inward. The shorter side's max determines how much water that position can trap — the taller side is guaranteed to be at least as high.

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]) {
      if (height[left] >= maxLeft) {
        maxLeft = height[left];
      } else {
        water += maxLeft - height[left];
      }
      left++;
    } else {
      if (height[right] >= maxRight) {
        maxRight = height[right];
      } else {
        water += maxRight - height[right];
      }
      right--;
    }
  }
  return water;
}

Tradeoff: O(n) time, O(1) space. The key insight: if height[left] <= height[right], the left side is the bottleneck — maxLeft determines the water at left regardless of what's to the right (the right is guaranteed >= height[right] >= height[left]). This is the optimal answer HubSpot expects.

HubSpot-specific tips

Start with the formula to ground the interviewer: 'Water at position i = min(maxLeft, maxRight) - height[i].' Then present the two-pointer approach as the O(1) space optimization of the prefix-max approach. HubSpot interviewers want to see you justify why moving the shorter pointer is safe: 'The shorter side is the bottleneck — whatever is on the taller side doesn't matter because min(...) picks the shorter.' Draw a diagram for the example if possible.

Common mistakes

  • Moving the taller pointer instead of the shorter — the bottleneck argument breaks and the algorithm produces incorrect results.
  • Not updating maxLeft/maxRight before computing water — using a stale max gives wrong water amounts.
  • Subtracting height[i] before checking if it exceeds the current max — can produce negative water contributions.
  • Confusing the direction: maxLeft tracks the max seen from the left moving right; maxRight from the right moving left.

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 3D elevation map using a min-heap + BFS.
  • Container With Most Water (LC 11) — maximize area between two bars (similar two-pointer reasoning).
  • What if bars have variable widths — how does the formula change?

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 moving the shorter pointer safe?

If height[left] <= height[right], we know the right side has a bar at least as tall as the current left. So min(maxLeft, something >= height[right]) = maxLeft (provided height[left] < maxLeft). The water calculation is safe.

What if two bars are equal height?

The condition uses <=, so equal bars process the left pointer. This is arbitrary — either choice produces the correct answer because both sides would contribute zero water at that step.

Can the formula ever give a negative value?

No — min(maxLeft, maxRight) is always >= height[i] because maxLeft and maxRight include height[i] itself. The subtraction is always non-negative.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →