Trapping Rain Water

Time: O(n)

Space: O(1)

Intuition

Same as LeetCode 42. Two-pointer approach: water at each position is limited by the shorter of the max heights seen from left and right. Two pointers converge inward, always processing the shorter side.

Algorithm

1left=0, right=n-1, leftMax=0, rightMax=0, water=0.
2While left < right: if height[left] <= height[right]: leftMax=max(leftMax,height[left]). water+=leftMax-height[left]. left++.
3Else: rightMax=max(rightMax,height[right]). water+=rightMax-height[right]. right--.

Example Walkthrough

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

1.Two-pointer fills: total trapped = 6.

Output: 6

Common Pitfalls

•Process the shorter side â€” the shorter boundary determines how much water is trapped.

Trapping Rain Water.java

Java

// Approach: Two-pointer approach. Track left max and right max; water at i = min(leftMax, rightMax) - height[i].
// Time: O(n) Space: O(1)
class Solution {
    public int maxWater(int arr[]) {
        int n = arr.length;
        int pre[] = new int[n];
        int post[] = new int[n];
        pre[0] = arr[0];
        int ans = 0;
        post[n - 1] = arr[n - 1];
        for (int i = 1; i < n; i++)
            pre[i] = Math.max(pre[i - 1], arr[i]);

        for (int j = n - 2; j >= 0; j--)
            post[j] = Math.max(post[j + 1], arr[j]);

        for (int i = 0; i < n; i++)
            ans += Math.min(pre[i], post[i]) - arr[i];
        
        return ans;
    }
}

Was this solution helpful?