Q25: How do you solve the Trapping Rain Water problem in O(n) time and O(1) space?

Use Two Pointers (left = 0, right = len - 1) maintaining leftMax and rightMax. At each step, if height[left] < height[right]:

If height[left] >= leftMax, update leftMax = height[left].
Else, add leftMax - height[left] to total water.
Increment left. Else, process right pointer symmetrically.

Trapping Rain Water Two-Pointer Solution

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

💡 Calculates trapped water at boundary limits while moving inward.

Key Takeaways

Water trapped at index $i$ depends on $min( ext{leftMax}, ext{rightMax}) - ext{height}[i]$.
Two pointers process lower boundary limits inward in $O(n)$ time and $O(1)$ space.

Knowledge Check

What determines the trapped water height at any index i?

Q25: How do you solve the Trapping Rain Water problem in O(n) time and O(1) space?

STAY UPDATED WITH BYTES!