Trapping Rain Water

Hard

📘 Problem Statement

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

🔍 Example

Example 1:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]

Output: 6

Explanation: The elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water are being trapped.

Example 2:

Input: [4,2,0,3,2,5]

Output: 9

🧠 Key Insight

  • Water can only be trapped if there are higher bars on both sides
  • At any position, the amount of water trapped depends on the minimum of the maximum heights to the left and right, minus the height at the current position
  • We can use a two-pointer approach to efficiently calculate this without pre-computing left and right max arrays

🛠️ Solution 

def trap(height):
    if not height or len(height) < 3:
        return 0
    
    left, right = 0, len(height) - 1
    left_max = height[left]
    right_max = height[right]
    water = 0
    
    while left < right:
        if left_max < right_max:
            left += 1
            # Update left_max if current height is greater
            left_max = max(left_max, height[left])
            # Add trapped water at current position
            water += left_max - height[left]
        else:
            right -= 1
            # Update right_max if current height is greater
            right_max = max(right_max, height[right])
            # Add trapped water at current position
            water += right_max - height[right]
    
    return water

🕒 Time Complexity: \(O(n)\) where n is the length of the height array

📦 Space Complexity: \(O(1)\) as we only use constant extra space

💡 Explanation

  1. We use two pointers, left and right, starting from the beginning and end of the array.
  2. We maintain two variables, left_max and right_max, to track the maximum height seen so far from the left and right sides.
  3. At each step, we move the pointer from the side with the smaller maximum height:
    • If left_max < right_max, we move the left pointer and update water trapped at that position
    • Otherwise, we move the right pointer and update water trapped at that position
  4. The key insight is that if left_max < right_max, then the water trapped at the left pointer position is determined by left_max, regardless of heights between left and right.
  5. Similarly, if right_max < left_max, the water trapped at the right pointer position is determined by right_max.
  6. This approach ensures we only need to traverse the array once.