Trapping Rain Water | Two Pointers & Stack | Array

Overview

Trapping Rain Water is a classic problem that calculates how much rainwater can be trapped between bars of different heights. The key insight: water trapped at position i equals min(max_left, max_right) - height[i], where max_left and max_right are the maximum heights to the left and right.

Multiple approaches:

Two Pointers - O(n) time, O(1) space
Stack - O(n) time, O(n) space
Dynamic Programming - O(n) time, O(n) space
Brute Force - O(n²) time, O(1) space

Trapping rain water is particularly useful for:

Understanding two-pointer technique
Stack-based solutions
Space-time trade-offs
Real-world water collection problems

Pattern 1: Two Pointers Approach

Most efficient solution using two pointers.

function trap(height: number[]): number {
  if (height.length === 0) return 0;
  
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;
  
  while (left < right) {
    if (height[left] < height[right]) {
      // Process left side
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }
      left++;
    } else {
      // Process right side
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }
  
  return water;
}

Time: O(n), Space: O(1)

Explanation: Process side with smaller height. Water trapped depends on minimum of left/right max.

Pattern 2: Stack Approach

Use monotonic stack to find trapped water.

function trapStack(height: number[]): number {
  const stack: number[] = [];
  let water = 0;
  
  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!;
      
      if (stack.length === 0) break;
      
      const left = stack[stack.length - 1];
      const width = i - left - 1;
      const trappedHeight = Math.min(height[i], height[left]) - height[bottom];
      water += width * trappedHeight;
    }
    
    stack.push(i);
  }
  
  return water;
}

Time: O(n), Space: O(n)

Explanation: Stack stores indices of decreasing heights. When taller bar found, calculate trapped water.

Pattern 3: Dynamic Programming Approach

Precompute left and right maximums.

function trapDP(height: number[]): number {
  const n = height.length;
  if (n === 0) return 0;
  
  const leftMax = new Array(n).fill(0);
  const rightMax = new Array(n).fill(0);
  
  // Compute left maximums
  leftMax[0] = height[0];
  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i]);
  }
  
  // Compute right maximums
  rightMax[n - 1] = height[n - 1];
  for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i]);
  }
  
  // Calculate trapped water
  let water = 0;
  for (let i = 0; i < n; i++) {
    water += Math.min(leftMax[i], rightMax[i]) - height[i];
  }
  
  return water;
}

Time: O(n), Space: O(n)

Explanation: For each position, water = min(left_max, right_max) - height.

Pattern 4: Brute Force Approach

Check all positions for trapped water.

function trapBruteForce(height: number[]): number {
  let water = 0;
  
  for (let i = 0; i < height.length; i++) {
    let leftMax = 0;
    let rightMax = 0;
    
    // Find max to the left
    for (let j = 0; j < i; j++) {
      leftMax = Math.max(leftMax, height[j]);
    }
    
    // Find max to the right
    for (let j = i + 1; j < height.length; j++) {
      rightMax = Math.max(rightMax, height[j]);
    }
    
    const trapped = Math.min(leftMax, rightMax) - height[i];
    water += Math.max(0, trapped);
  }
  
  return water;
}

Time: O(n²), Space: O(1)

Not recommended for large inputs.

Pattern 5: Trapping Rain Water II (2D)

Trapped water in 2D elevation map.

function trapRainWater(heightMap: number[][]): number {
  if (heightMap.length === 0) return 0;
  
  const rows = heightMap.length;
  const cols = heightMap[0].length;
  const visited = Array(rows).fill(null).map(() => Array(cols).fill(false));
  
  // Min heap: [height, row, col]
  const heap: Array<[number, number, number]> = [];
  
  // Add boundary cells to heap
  for (let i = 0; i < rows; i++) {
    heap.push([heightMap[i][0], i, 0]);
    heap.push([heightMap[i][cols - 1], i, cols - 1]);
    visited[i][0] = true;
    visited[i][cols - 1] = true;
  }
  
  for (let j = 1; j < cols - 1; j++) {
    heap.push([heightMap[0][j], 0, j]);
    heap.push([heightMap[rows - 1][j], rows - 1, j]);
    visited[0][j] = true;
    visited[rows - 1][j] = true;
  }
  
  heap.sort((a, b) => a[0] - b[0]);
  
  let water = 0;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  
  while (heap.length > 0) {
    const [currentHeight, row, col] = heap.shift()!;
    
    for (const [dr, dc] of directions) {
      const newRow = row + dr;
      const newCol = col + dc;
      
      if (newRow >= 0 && newRow < rows && 
          newCol >= 0 && newCol < cols && 
          !visited[newRow][newCol]) {
        
        visited[newRow][newCol] = true;
        
        if (heightMap[newRow][newCol] < currentHeight) {
          water += currentHeight - heightMap[newRow][newCol];
          heap.push([currentHeight, newRow, newCol]);
        } else {
          heap.push([heightMap[newRow][newCol], newRow, newCol]);
        }
        
        heap.sort((a, b) => a[0] - b[0]);
      }
    }
  }
  
  return water;
}

Time: O(rows cols log(rows cols)), Space: O(rows cols)

Explanation: Use priority queue starting from boundaries, process cells in height order.

Pattern 6: Container With Most Water

Find two lines that form container with most water.

function maxArea(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let maxWater = 0;
  
  while (left < right) {
    const width = right - left;
    const minHeight = Math.min(height[left], height[right]);
    maxWater = Math.max(maxWater, width * minHeight);
    
    // Move pointer with smaller height
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  
  return maxWater;
}

Time: O(n), Space: O(1)

Key insight: Always move pointer with smaller height.

Pattern 7: Trapping Rain Water with Stack (Optimized)

Optimized stack approach.

function trapStackOptimized(height: number[]): number {
  const stack: number[] = [];
  let water = 0;
  let current = 0;
  
  while (current < height.length) {
    while (stack.length > 0 && height[current] > height[stack[stack.length - 1]]) {
      const top = stack.pop()!;
      
      if (stack.length === 0) break;
      
      const distance = current - stack[stack.length - 1] - 1;
      const boundedHeight = Math.min(height[current], height[stack[stack.length - 1]]) - height[top];
      water += distance * boundedHeight;
    }
    
    stack.push(current++);
  }
  
  return water;
}

Time: O(n), Space: O(n)

Pattern 8: Trapping Rain Water (One Pass)

Calculate in single pass without precomputation.

function trapOnePass(height: number[]): number {
  let water = 0;
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  
  while (left <= right) {
    if (leftMax < rightMax) {
      // Process left
      if (height[left] > leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }
      left++;
    } else {
      // Process right
      if (height[right] > rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }
  
  return water;
}

Time: O(n), Space: O(1)

Pattern 9: Trapping Rain Water (Space Optimized DP)

Reduce space from O(n) to O(1).

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

Time: O(n), Space: O(1)

Pattern 10: Trapping Rain Water (Edge Cases)

Handle edge cases properly.

function trapWithEdgeCases(height: number[]): number {
  if (height.length < 3) return 0;
  
  // Find first and last non-zero heights
  let start = 0;
  while (start < height.length && height[start] === 0) start++;
  
  let end = height.length - 1;
  while (end >= 0 && height[end] === 0) end--;
  
  if (start >= end) return 0;
  
  // Use two pointers on valid range
  let left = start;
  let right = end;
  let leftMax = height[left];
  let rightMax = height[right];
  let water = 0;
  
  while (left < right) {
    if (leftMax < rightMax) {
      left++;
      if (height[left] < leftMax) {
        water += leftMax - height[left];
      } else {
        leftMax = height[left];
      }
    } else {
      right--;
      if (height[right] < rightMax) {
        water += rightMax - height[right];
      } else {
        rightMax = height[right];
      }
    }
  }
  
  return water;
}

Time: O(n), Space: O(1)

When to Use Each Approach

Two Pointers (Recommended):

O(1) space requirement
Simple and efficient
Use when: Space is constrained

Stack Approach:

Intuitive for some problems
Useful for variations
Use when: Need to track multiple boundaries

Dynamic Programming:

Easy to understand
Precompute all maxes
Use when: Need to query multiple times

Brute Force:

Simple but slow
Use when: Small input size

Template (Two Pointers)

function trapTemplate(height: number[]): number {
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  let water = 0;
  
  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left];
      } else {
        water += leftMax - height[left];
      }
      left++;
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right];
      } else {
        water += rightMax - height[right];
      }
      right--;
    }
  }
  
  return water;
}

Template (Stack)

function trapStackTemplate(height: number[]): number {
  const stack: number[] = [];
  let water = 0;
  
  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!;
      if (stack.length === 0) break;
      
      const left = stack[stack.length - 1];
      const width = i - left - 1;
      const trappedHeight = Math.min(height[i], height[left]) - height[bottom];
      water += width * trappedHeight;
    }
    stack.push(i);
  }
  
  return water;
}

Time and Space Complexity Summary

Two pointers: O(n) time, O(1) space
Stack: O(n) time, O(n) space
Dynamic programming: O(n) time, O(n) space
Brute force: O(n²) time, O(1) space
2D version: O(rows cols log(rows cols)) time, O(rows cols) space

Practice Tips

Understand formula - Water = min(left_max, right_max) - height
Two pointers - Process side with smaller height
Stack approach - Track decreasing heights
Edge cases - Empty array, all zeros, single element
Visualization - Draw bars to understand trapped water

Common Mistakes

Wrong formula - Not using min of left/right max
Index errors - Off-by-one in pointer movement
Negative water - Not handling when height > min(max_left, max_right)
Edge cases - Not handling empty or single element arrays
Stack empty - Not checking if stack is empty before accessing

Related Concepts

Two Pointers - Core technique
Monotonic Stack - Alternative approach
Dynamic Programming - Precomputation approach
Greedy Algorithm - Two pointers uses greedy choice

Trapping rain water is a classic interview problem. Master the two-pointer approach for optimal O(n) time and O(1) space solution, and understand stack approach for variations in coding interviews.