Java: Trapping Rain Water

Thought Process

To solve the "Trapping Rain Water" problem, we use a two-pointer approach using left and right arrays. The idea is to calculate the maximum height to the left and maximum height to the right of each bar. The amount of water trapped at each bar is determined by the minimum of these two heights minus the height of the current bar. We first compute the left and right arrays to store the maximum heights. Then, we iterate through the array, calculate the trapped water for each bar, and accumulate the result. 

class Solution {
    public int trap(int[] height) {
        
        int sz = height.length;
        int[] leftMax = new int[sz];
        int[] rightMax = new int[sz];
        int waterTrapped = 0;

        leftMax[0]     = height[0];
        rightMax[sz-1] = height[sz-1];

        for(int i=1;i<height.length;i++)
            leftMax[i] = Math.max(height[i],leftMax[i-1]);
        
        for(int i=sz-2;i>=0;i--)
            rightMax[i] = Math.max(height[i],rightMax[i+1]);

        for(int i=0;i<sz;i++)
            waterTrapped += Math.abs(Math.min(rightMax[i],leftMax[i])-height[i]);

        return waterTrapped;
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the array three times, making it linear in time complexity.

Space Complexity: O(n)

The algorithm uses two additional arrays of size 'n' to store the left and right maximum heights.

Code copied!