Skip to main content

42. Trapping Rain Water

hardAsked at Juniper Networks

Calculate how much water a histogram can trap after rain using two pointers. Juniper asks this because computing buffer occupancy in a traffic shaping scenario — where the water level is analogous to the minimum available buffer capacity bounded by adjacent queues — is a real systems analogy. It tests both the O(n) two-pointer insight and the ability to explain the invariant under pressure.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2026-Q1)— Reported in Juniper SWE onsite reports as a classic hard problem used to probe algorithmic reasoning depth.
  • Blind (2025-12)— Multiple Juniper threads cite Trapping Rain Water as a must-prep hard problem for senior SWE and systems 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. Precompute max-left and max-right arrays

For each position, the water it holds = min(maxLeft[i], maxRight[i]) - height[i]. Precompute prefix max from left and suffix max from right.

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);
  for (let i = 1; i < n; i++) maxLeft[i] = Math.max(maxLeft[i - 1], height[i - 1]);
  for (let i = n - 2; i >= 0; i--) maxRight[i] = Math.max(maxRight[i + 1], height[i + 1]);
  let water = 0;
  for (let i = 0; i < n; i++) {
    const level = Math.min(maxLeft[i], maxRight[i]);
    if (level > height[i]) water += level - height[i];
  }
  return water;
}

Tradeoff: O(n) time, O(n) space. Easy to understand and verify. Good starting point; then optimize to O(1) space.

2. Two pointers — O(1) space

Maintain left and right pointers and track leftMax and rightMax. Move the pointer on the side with the smaller max. The key invariant: the water at the smaller-max side is fully determined by that max.

Time
O(n)
Space
O(1)
function trap(height) {
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let 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 invariant: when height[left] < height[right], we know rightMax is at least height[right], so water at left is fully determined by leftMax. This eliminates the need for the right-scan array.

Juniper Networks-specific tips

Walk through the two-pointer invariant carefully — Juniper interviewers will push back to make sure you can defend it. 'When height[left] < height[right], I know there is a wall at least as tall as height[right] on the right, so the water at position left is bounded only by leftMax — I don't need to know the exact rightMax.' This is a subtle but crucial distinction. Present the O(n) space solution first to establish correctness, then derive the O(1) version.

Common mistakes

  • Updating leftMax/rightMax after computing water instead of before — you need the max up to but not including the current position.
  • Using height[left] <= height[right] vs < — either works for the comparison, but be consistent about which side moves.
  • Not handling the case where height[i] >= max — no water is added; only update the max.
  • Initializing leftMax and rightMax to height[0] and height[n-1] instead of 0 — leads to incorrect water computation at the boundaries.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • Trapping Rain Water II (LC 407) — the 3D version; requires a min-heap over the boundary.
  • Container With Most Water (LC 11) — related two-pointer problem but asks for maximum area, not total trapped water.
  • How would you compute the maximum packet buffer occupancy across a sequence of interface rate measurements?

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 exact rightMax when processing left?

When height[left] < height[right], we know height[right] is at least height[right] tall — and rightMax >= height[right]. So the right boundary is guaranteed to be >= height[right] > height[left]. The water at left is solely bounded by leftMax.

What does leftMax represent exactly?

leftMax is the maximum height seen so far from the left, excluding the current position. It is the height of the tallest left wall available to hold water at position left.

Does the order of moving left vs right matter?

The direction is determined by which side has the smaller max. This is the key decision rule — moving the smaller side is always safe because the larger side guarantees a sufficient boundary.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →