Leet Code 42:- Trapping rain water solution

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Here we have to calculate the total trapped water area under this blocks.

To solve this problem, best approach is to use the double counter. Will start from each end ( left and right).

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

Illustration:-

In this approach we will loop over the array only once and not using any space to store the result, so here time O(n) and space O(1).