Trapping Rain Water Problem

Problem Description
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.

Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: 6 units of water can be trapped (the blue section represents water).

Solution Approach
This problem can be solved using multiple methods. We start from the most intuitive brute-force approach and gradually optimize to the optimal solution.

Method 1: Brute Force (Column-wise Calculation)
Core Idea: For each bar, find the highest bar to its left and right, then calculate the amount of water that can be trapped at that bar.

Steps:

1. Iterate over each element in the array (representing the current bar).
2. Scan left to find the highest bar height left_max to the left of the current bar.
3. Scan right to find the highest bar height right_max to the right of the current bar.
4. Water trapped at current bar = min(left_max, right_max) - current bar height.
5. If the result is negative, treat it as 0.
6. Sum up the water trapped for all bars.

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

Method 2: Dynamic Programming (Preprocessing Max Values)
Optimization Idea: Precompute the left and right maximum heights for each position to avoid repeated scans.

Steps:

1. Create two arrays left_max and right_max.
2. left_max[i] represents the highest bar height to the left of position i (including i).
   • left_max[0] = height[0]
   • left_max[i] = max(left_max[i-1], height[i])
3. right_max[i] represents the highest bar height to the right of position i (including i).
   • right_max[n-1] = height[n-1]
   • right_max[i] = max(right_max[i+1], height[i])
4. Iterate over each position and calculate trapped water: min(left_max[i], right_max[i]) - height[i]

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

Method 3: Two Pointers Approach (Optimal Solution)
Optimization Idea: Optimize space complexity based on dynamic programming by using two pointers traversing from both ends toward the center.

Steps:

1. Initialize left = 0, right = n-1.
2. Initialize left_max = 0, right_max = 0 (to record the left and right maximum heights encountered during traversal).
3. While left < right:
   • If height[left] < height[right]:
     • If height[left] ≥ left_max, update left_max.
     • Otherwise, accumulate trapped water: left_max - height[left].
     • left++
   • Else:
     • If height[right] ≥ right_max, update right_max.
     • Otherwise, accumulate trapped water: right_max - height[right].
     • right--

Key Insight: We always move the pointer on the side with the smaller height because the amount of trapped water is determined by the shorter side.

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

Code Implementation (Two Pointers Approach)

def trap(height):
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    result = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                result += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                result += right_max - height[right]
            right -= 1
    
    return result

Summary
The trapping rain water problem tests the understanding of array operations and two-pointer techniques. The optimization process from brute force to dynamic programming and then to the two-pointer approach reflects common optimization strategies in algorithm design: reducing repeated calculations through preprocessing and then lowering space complexity through spatial optimization.