Leetcode - Trapping Rain Water Solution

Calculating how much rainwater can be trapped between bars looks like a complex geometry problem at first. Water at any position is limited by the shorter of the two tallest bars on either side. This observation led me to a two pointer solution that runs in O(n) time instead of the O(n²) approach I started with.

Understanding the Problem

Given an elevation map represented as an array of heights, calculate how much rainwater can be trapped. Water is trapped at a position when taller bars exist on both sides. The smaller of the maximum heights on the two sides sets the water level. Subtract the height at position i to calculate the water depth, with a minimum depth of zero.

My First Approach

My initial solution was straightforward but inefficient. For each position, I would find the maximum height on the left and right, then calculate the trapped water.

function trapNaive(heights) {
  let total = 0;

  for (let i = 0; i < heights.length; i++) {
    // Find max on left
    let leftMax = 0;
    for (let j = 0; j < i; j++) {
      leftMax = Math.max(leftMax, heights[j]);
    }

    // Find max on right
    let rightMax = 0;
    for (let j = i + 1; j < heights.length; j++) {
      rightMax = Math.max(rightMax, heights[j]);
    }

    // Water trapped at this position
    const water = Math.min(leftMax, rightMax) - heights[i];
    if (water > 0) {
      total += water;
    }
  }

  return total;
}

This approach takes O(n²) time because it scans both sides again for each position.

The Two Pointers Insight

The optimized solution uses two pointers starting from both ends and tracks the maximum heights seen so far. We always process the side with the smaller maximum because it limits the water level.

The algorithm works like this:

• Start with pointers at both ends
• Track the maximum height seen on each side as we move
• Process from the side with the smaller maximum (the limiting side)
• Move inward, updating maximums as we go

Each pointer moves toward the center, and the algorithm processes each position once.

Two pointer implementation

function trap(heights) {
  let left = 0;
  let right = heights.length - 1;
  let storedWater = 0;
  let leftMax = 0; // Max height seen from left
  let rightMax = 0; // Max height seen from right

  while (left <= right) {
    // Process from the side with smaller max (the limiting side)
    if (leftMax <= rightMax) {
      // Process left side
      if (heights[left] < leftMax) {
        // Can trap water here
        storedWater += leftMax - heights[left];
      } else {
        // Update leftMax
        leftMax = heights[left];
      }
      left++;
    } else {
      // Process right side
      if (heights[right] < rightMax) {
        // Can trap water here
        storedWater += rightMax - heights[right];
      } else {
        // Update rightMax
        rightMax = heights[right];
      }
      right--;
    }
  }

  return storedWater;
}

Why the limiting side is safe

The algorithm works because we always process the side with the smaller maximum:

• For a bar below the smaller known maximum, min(leftMax, rightMax) determines the water level at that position
• By processing the limiting side, we know the water level cannot exceed that side's maximum
• We do not need to know future values on the other side because we are already processing the limiting factor
• As we move inward, we update our maximums, ensuring we always have accurate information

Step by Step Example

For [0,1,0,2,1,0,1,3,2,1,2,1], the pointers move as follows:

• Initial: left=0, right=11, leftMax=0, rightMax=0
• leftMax <= rightMax, process left: height[0]=0, leftMax=0, no water (height equals max), leftMax stays 0, left=1
• leftMax <= rightMax, process left: height[1]=1, leftMax=1, no water, leftMax=1, left=2
• leftMax > rightMax, process right: height[11]=1, rightMax=1, no water, right=10
• leftMax <= rightMax, process left: height[2]=0, leftMax=1, water += 1-0 = 1, left=3
• Continue processing...

The smaller known maximum is sufficient to calculate water at the selected position. The other side already has a boundary at least that high.

Why This Approach Is Better

Time Complexity: O(n)

• Single pass through the array
• Each element is processed exactly once
• No nested loops needed

Space Complexity: O(1)

• Only using a few variables for pointers and maximums
• No additional data structures needed

Efficiency

• Reduced from O(n²) to O(n)
• Much faster for large inputs

Common Pitfalls

When implementing this, watch out for:

1. Processing the wrong side: Always process from the side with the smaller maximum
2. Not updating maximums correctly: Make sure to update leftMax/rightMax when you encounter a taller bar
3. Edge cases: Empty arrays or arrays with less than 3 elements cannot trap water

Rainwater summary

• Two pointers from both ends can solve many array problems efficiently
• Track maximums as you go instead of recalculating them
• Process the limiting side first because it determines the water level
• This reduces time complexity from O(n²) to O(n) with O(1) space

Tracking the maximums while moving inward gives O(n) time and O(1) space.