40. Trapping Rain Water

Use left and right pointers moving inward. Water at each position is determined by the minimum of left_max and right_max minus the height at that position.

Approach

1. Two pointers: left=0, right=n-1.
2. Track left_max and right_max.
3. Process the side with the smaller max (that side's water level is determined).
4. Water at position = side_max - height[position].

Complexity

• Time: O(n)
• Space: O(1)

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, water = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) leftMax = height[left];
                else water += leftMax - height[left];
                left++;
            } else {
                if (height[right] >= rightMax) rightMax = height[right];
                else water += rightMax - height[right];
                right--;
            }
        }
        return water;
    }
}