Leetcode - Trapping Rain Water Solution

Calculating how much rainwater can be trapped between bars looks like a complex geometry problem at first. But once I understood the key insight, the solution became surprisingly elegant. Water at any position is limited by the shorter of the two tallest bars on either side. This realization 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 there are bars on both sides that are taller than the current position. The amount of water trapped at position i is determined by the minimum of the maximum heights on the left and right sides.

My First Approach

My initial solution was straightforward but inefficient. For each position, I'd 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 works, but it's O(n²) because for each position, I'm scanning the entire left and right sides. For large arrays, this becomes too slow. I needed a better approach.

The Two Pointers Insight

The key insight for the optimized solution is to use two pointers starting from both ends, tracking the maximum heights seen so far. Here's the crucial realization: we should always process from the side with the smaller maximum because that's the limiting factor for water trapping.

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

This way, we only need one pass through the array!

The Solution

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;
}

How It Works

The algorithm works because of this key insight: we always process from the side with the smaller maximum. Here's why this guarantees correctness:

• The water level at any position is limited by min(leftMax, rightMax)
• By processing the limiting side, we know the water level can't exceed that side's maximum
• We don't need to know future values on the other side because we're already processing the limiting factor
• As we move inward, we update our maximums, ensuring we always have accurate information

Step-by-Step Example

Let me trace through [0,1,0,2,1,0,1,3,2,1,2,1]:

• 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 left: height[2]=0, leftMax=1, water += 1-0 = 1, left=3
• Continue processing...

The key is that we're always processing from the limiting side, so we can calculate water trapped without needing to know all future values.

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 can't trap water

Key Takeaways

• 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 - this is the key insight
• This reduces time complexity from O(n²) to O(n) with O(1) space

The two pointers technique combined with tracking maximums makes what initially seemed like a complex problem quite elegant. Once you understand the pattern, you'll see it applies to many similar problems.