Crack The Backend

Algorithms

Trapping Rain Water

HardLast updated: 02/05/2026, 16:00:00 PST
01

Problem Statement

Given n non-negative integers height[i] representing an elevation map where the width of each bar is 1, compute how much water can be trapped after rain. Water is trapped between bars; each bar has unit width.

  • At index i, the water level above the bar is limited by the minimum of the maximum height to the left and the maximum height to the right. So water at i = max(0, min(maxLeft, maxRight) - height[i]).
  • We can compute this with two passes (left max and right max arrays) or with two pointers in one pass.
02

Key Observations

  • For each index i, the trapped water above it is min(maxLeft[i], maxRight[i]) - height[i] (if positive), where maxLeft[i] is the max height in [0..i] and maxRight[i] is the max in [i..n-1].
  • Two-pointer approach: Maintain left and right and maxL, maxR (max height seen so far from left and from right). The water at the current position (whichever side we process) is determined by the smaller of maxL and maxR (because that side's "wall" is the bottleneck). So if height[left] <= height[right], the water at left is maxL - height[left] (and we update maxL and left++). Else we process from the right similarly.
03

Approach

High-level: left=0, right=n-1, maxL=0, maxR=0, total=0. While left < right: if height[left] <= height[right], water at left is max(0, maxL - height[left]); update maxL, left++. Else: water at right is max(0, maxR - height[right]); update maxR, right--. Add water to total. Return total.

Steps:

  1. left=0, right=n-1, maxL=0, maxR=0, total=0.
  2. While left < right: if height[left] <= height[right]: total += max(0, maxL - height[left]), maxL = max(maxL, height[left]), left++. Else: total += max(0, maxR - height[right]), maxR = max(maxR, height[right]), right--.
  3. Return total.
04

Implementation

Java
public int trap(int[] height) {
    int left = 0, right = height.length - 1, maxL = 0, maxR = 0, total = 0;

    while (left < right) {
        if (height[left] <= height[right]) {
            if (height[left] >= maxL) {
                maxL = height[left];
            }
            else {
                total += maxL - height[left];
            }

            left++;
        }
        else {
            if (height[right] >= maxR) {
                maxR = height[right];
            }
            else {
                total += maxR - height[right];
            }

            right--;
        }
    }

    return total;
}
05

Test Cases

Example 1

Input
height = [0,1,0,2,1,0,1,3,2,1,2,1]
Expected
6
Explanation
6 units of rain trapped.
06

Complexity Analysis

  • Time: O(n).
  • Space: O(1).
07

Follow-ups

  • Trapping Rain Water II: 2D elevation map.