42. Trapping Rain Water

📝 Problem Details

• Title: 42. Trapping Rain Water
• Link: https://leetcode.com/problems/trapping-rain-water/
• Difficulty: Hard
• Tags/Categories: Two-Pointers

💭What Were My Initial Thoughts?

• The naïve approach would be to check each element and calculate how much water it can trap.
• The water trapped at an index i is determined by the minimum of the maximum height to its left and right, minus its own height.
• A brute force solution would involve nested loops to find left and right maximums, resulting in O(n²) time complexity.
• We need a more optimal solution, likely using dynamic programming or two pointers.

💡 Explanation of Solution

- use two pointers left and right starting at both ends
- keep track of maxLef and maxRight
- if height[left] < height[right]
	- process left and move it right
- otherwise, process right and move it left
- this ensures we always process the smaller boundary first 

⌛ Complexity Analysis

Tiem Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    int trap(vector<int>& height) {
        int i = 0;
        int j = height.size()-1;
 
        int maxLeft = height[i];
        int maxRight = height[j];
        int result = 0;
 
        while(i < j){
            if(maxLeft <= maxRight){
                i++;
                maxLeft = max(maxLeft, height[i]);
                result += maxLeft - height[i];
            } else {
                j--;
                maxRight = max(maxRight, height[j]);
                result += maxRight - height[j];
            }
        }
        return result;
    }
};