Trapping Rain Water

Approach Summary

Track max height from left and right. Water at each position is min(maxLeft, maxRight) - height. Move the pointer with the smaller max.

Full Solution & Approach

Water collects above a bar only when there is higher ground on both sides. The water on top of bar i is min(max height to its left, max height to its right) minus height[i]. Precomputing prefix and suffix maximums gives the answer directly in one extra pass, but the two-pointer version does it with O(1) space. Maintain leftMax and rightMax as you converge from both ends with two pointers. When leftMax is smaller, the water above the left pointer is fully determined by leftMax (rightMax can only be larger or equal), so add leftMax - height[left] and advance left, updating leftMax. Mirror on the right. The invariant that makes this safe: for the pointer on the side with the smaller running max, the other side's max is already at least as large, so the binding constraint is known.

Each bar is visited once by one of the two pointers — O(n) time. Only two running maxima and the pointers — O(1) space.

Solution Code

Solution

def trap(height: list[int]) -> int:
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1
    return water

function trap(height) {
  if (!height.length) return 0;
  let left = 0, right = height.length - 1;
  let leftMax = 0, rightMax = 0;
  let water = 0;
  while (left < right) {
    if (height[left] < height[right]) {
      leftMax = Math.max(leftMax, height[left]);
      water += leftMax - height[left];
      left++;
    } else {
      rightMax = Math.max(rightMax, height[right]);
      water += rightMax - height[right];
      right--;
    }
  }
  return water;
}

public int trap(int[] height) {
    if (height.length == 0) return 0;
    int left = 0, right = height.length - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

int trap(const vector<int>& height) {
    if (height.empty()) return 0;
    int left = 0, right = (int)height.size() - 1;
    int leftMax = 0, rightMax = 0, water = 0;
    while (left < right) {
        if (height[left] < height[right]) {
            leftMax = max(leftMax, height[left]);
            water += leftMax - height[left];
            left++;
        } else {
            rightMax = max(rightMax, height[right]);
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

Edge Cases to Watch

Monotonically increasing heights — no water at all
Flat profile with a dip — water fills the dip
Two tall towers sandwiching short bars — the classic full trap
Empty or single-element array — return 0

How to Recognize This Pattern

Water trapped between bars
Classic two-pointer/DP hybrid

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)