Trapping Rain Water

XXX. Trapping Rain Water

Array

Two Pointer

Problem Statement:

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

• Each element represents height of wall
• Width between walls is 1 unit
• Calculate total units of water trapped

Implementation:

public int trap(int[] height) {
    if (height == null || height.length == 0) 
        return 0;
    
    int left = 0;                          // Left pointer
    int right = height.length - 1;         // Right pointer
    int leftH = height[left];              // Max height from left
    int rightH = height[right];            // Max height from right
    
    int water = 0;                         // Total trapped water
    
    while (left < right) {
        if (height[left] < height[right]) {
            left++;                         // Move left pointer
            // Add trapped water at current position
            water += Math.max(0, leftH - height[left]);
            // Update max height from left
            leftH = Math.max(height[left], leftH);
        } else {
            right--;                        // Move right pointer
            // Add trapped water at current position
            water += Math.max(0, rightH - height[right]);
            // Update max height from right
            rightH = Math.max(height[right], rightH);
        }
    }
    
    return water;
}

Complexity:

Time Complexity: O(n), single pass through array
Space Complexity: O(1), constant extra space

Key Points:

• **Two Pointer Technique**:
  • Start from both ends of array
  • Move pointer with smaller height
  • Track max height from both sides
• **Water Calculation**:
  • Water at position = min(maxLeft, maxRight) - height[i]
  • Only add positive water amounts
  • Update max heights after processing position
• **Optimization**:
  • No need to store max heights array
  • Process in single pass
  • Move towards higher wall for efficiency

Example:

For array [0,1,0,2,1,0,1,3,2,1,2,1]:

• Process steps:
  • Move from both ends toward center
  • Track max height seen from each side
  • Calculate trapped water at each step
• Total trapped water = 6 units

Understanding the Algorithm:

• **Why Two Pointers Work**:
  • Water trapped depends on shorter surrounding wall
  • Moving from smaller to larger height guarantees valid calculation
  • No need to consider walls beyond current max height
• **Implementation Details**:
  • Track current max height from both sides
  • Water can only be trapped if current height is less than max
  • Always move towards potentially higher walls