LeetCode Solution 42 - Trapping Rain Water

Problem Statement

Given an array height of non-negative integers where each element represents the elevation at that index, compute how much water can be trapped between the bars after raining.

Example 1:

Input:

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Output:

6

Explanation:

Water is trapped between indices where bars have lower heights.

Example 2:

Input:

height = [4,2,0,3,2,5]

Output:

9

---

Optimal Approach: Two Pointers

Why Two Pointers?

• Efficiently calculates trapped water without extra space.
• Maintains left and right maximum heights dynamically.
• Works in O(N) time complexity and O(1) space complexity.

Algorithm:

1. Initialize left = 0 and right = n - 1.
2. Maintain left_max and right_max.
3. Move the pointer pointing to the shorter bar inward.
4. If height[left] < height[right], update left_max and calculate water trapped.
5. Otherwise, update right_max and calculate trapped water.
6. Repeat until pointers meet.

---

C++ Code Implementation

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int left_max = 0, right_max = 0, water = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    water += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    water += right_max - height[right];
                }
                right--;
            }
        }
        return water;
    }
};

---

Step-by-Step Explanation

1. Initialize Two Pointers: left = 0, right = n - 1, left_max = 0, right_max = 0, and water = 0.
2. Move the Shorter Pointer:
   • If height[left] < height[right], process left.
   • Else, process right.
3. Update Maximum Heights:
   • If height[left] or height[right] is greater than its respective max, update it.
   • Otherwise, trapped water is max - height.
4. Continue Until Pointers Meet.

---

Dry Run

Input:

height = [0,1,0,2,1,0,1,3,2,1,2,1]

Execution:

Step	Left	Right	Left Max	Right Max	Water Collected
1	0	11	0	1	0
2	1	11	1	1	0
3	2	11	1	1	1
4	3	11	2	1	1
5	4	11	2	1	2
6	5	11	2	1	4
7	6	11	2	1	5
8	7	11	3	1	6

---

Alternative Approaches

Approach	Time Complexity	Space Complexity	Reason for Rejection
Brute Force	O(N^2)	O(1)	Too slow for large inputs
Dynamic Programming	O(N)	O(N)	Uses extra space for left & right max arrays
Two Pointers (Best)	O(N)	O(1)	Most efficient

---

Complexity Analysis

• Time Complexity: O(N) as we traverse the array once.
• Space Complexity: O(1) as we only use a few extra variables.

---

Conclusion

• Best Approach: Two Pointers.
• Further Practice:
  • Container With Most Water
  • Rain Water Trapping II

This solution efficiently computes Trapping Rain Water using Two Pointers, making it optimal for large inputs.