42. Trapping Rain Water

Hint

class Solution {
public:
    int trap(vector<int>& height)
    {
        // Pointer to the left end of the array
        // Pointer to the right end of the array
        // Maximum height seen from the left side
        // Maximum height seen from the right side
        // Variable to store the total amount of trapped water

        // Traverse the array until the left and right pointers meet
        while()
        {
            if()
            {
                // Move the left pointer one step to the right
                // Update leftMax if the new height is greater
                // Add the trapped water at the current position
            }
            else
            {
                // Move the right pointer one step to the left
                // Update rightMax if the new height is greater
                // Add the trapped water at the current position
            }
        }
        // Return the total amount of trapped water
    }
};

class Solution {
public:
    int trap(vector<int>& height)
    {
        int left = 0, right = height.size() - 1;
        int leftMax = height[left], rightMax = height[right];
        int res = 0;

        while(left < right)
        {
            if(leftMax < rightMax)
            {
                leftMax = max(leftMax, height[++left]);
                res += leftMax - height[left];
            }
            else
            {
                rightMax = max(rightMax, height[--right]);
                res += rightMax - height[right];
            }
        }
        return res;
    }
};

• T: $O(N)$
• S: $O(1)$