Trapping Rain Water

Difficulty: Hard

Problem

Imagine you have a row of walls (bars) of different heights. After it rains, water gets trapped in the gaps between taller walls. Given an array where each number represents the height of a wall, calculate the total amount of water that can be trapped between these walls.

Think of it like a cross-section of a container: water fills the low spots but can only rise as high as the SHORTER of the two boundary walls on either side.

Example

Input: height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Output: 6
Explanation: Looking at position 2 (height=0): the tallest wall to its left is 1, and the tallest to its right is 3. Water rises to min(1,3)=1, so 1 unit of water is trapped there. At position 5 (height=0): left max is 2, right max is 3, so water rises to 2, trapping 2 units. Adding up all positions: 0+0+1+0+1+2+1+0+0+1+0+0 = 6 units total.

Brute-force approach

For each position, find the max height on left and right, calculate water at that position.

Steps

  1. For each position i
  2. Find max height on left of i
  3. Find max height on right of i
  4. Water at i = min(leftMax, rightMax) - height[i]

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Recalculating max for each position
  • Same maxes computed multiple times
  • Very inefficient for large arrays

Optimal approach

Key insight: Water level at any position is limited by the shorter of the two boundary walls. By always processing the shorter side, we can calculate water correctly in O(n) time!

Two pointers: process from the side with smaller height, since water is bounded by the shorter wall.

Steps

  1. Place pointers at both ends of the array
  2. Track the maximum heights seen from left (leftMax) and right (rightMax)
  3. Compare heights at left and right pointers - process the SHORTER side
  4. If current height < max on that side, we trap water. Otherwise, update the max.
  5. Move the processed pointer inward. Repeat until pointers meet.

Time complexity: O(n) · Space complexity: O(1)