Skip to main content

42. Trapping Rain Water

hardAsked at Cohere

Calculate how much water can be trapped between bars after rain. Cohere asks this because the two-pointer insight — maintaining running maxima from both ends — mirrors how bidirectional attention masks are constructed in transformer architectures.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2026-Q1)— Multiple Cohere onsite reports list Trapping Rain Water as a hard problem that rewards candidates who derive the two-pointer insight.
  • Blind (2025-11)— Cohere engineering threads cite this as a high-signal problem separating strong candidates from the field.

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 rain water.

Example 2

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

Explanation: 9 units trapped.

Approaches

1. Prefix/suffix max arrays

Pre-compute the maximum height to the left and right of each position. Water at position 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), rightMax = new Array(n);
  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 and space. Very readable — a good starting point to establish the key formula.

2. Two-pointer O(1) space

Use two pointers from both ends. The side with the smaller max constrains the water level. Process that side and advance the pointer inward.

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 — optimal. The insight: when leftMax < rightMax, the left pointer's water is determined by leftMax regardless of what's on the right (it can only be taller).

Cohere-specific tips

Cohere interviewers reward candidates who derive the two-pointer insight rather than remembering it. The key intuition: 'The water level at any position is bounded by the shorter wall. If I know the left wall is shorter, the water above the left pointer is determined solely by leftMax — whatever is on the right can only be taller.' Verbalise this before writing the two-pointer code. Cohere engineers appreciate mathematical rigour, so be prepared to prove the correctness of the pointer movement rule.

Common mistakes

  • Updating leftMax or rightMax after computing water — update the max first, then compute water.
  • Using the wrong boundary for the pointer advance condition — the pointer on the side with the smaller height[pointer] (not max) advances.
  • Computing negative water — the formula min(leftMax, rightMax) - height[i] is always ≥ 0 by construction.
  • Confusing the prefix max with the current height — leftMax[i] is the global max up to i, not height[i].

Follow-up questions

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

  • Trapping Rain Water II (LC 407) — 3D elevation map, requires a min-heap.
  • Container With Most Water (LC 11) — simpler two-pointer variant.
  • How does the two-pointer technique relate to bidirectional context aggregation in attention mechanisms?

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 it matter which pointer advances?

The smaller of the two current heights determines which side's water computation is fully constrained. Advancing the larger-height side would leave an unconstrained computation. Always advance the side with the smaller height.

Can this be solved with a stack?

Yes — a monotonic decreasing stack approach also works in O(n) time, computing horizontal water layers. But the two-pointer approach is more elegant and avoids the stack.

What if all bars are the same height?

No water is trapped — min(leftMax, rightMax) = height[i] at every position, so each term is 0.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →