Trapping Rain Water – SchoolCodeHub

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.

Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

Solution

Approach 1:

Java

class Solution {
    public int trap(int[] height) {
        int res = 0;
        int max_left = height[0]; 
        int max_right = height[height.length -1];
        int lp = 0;
        int rp = height.length - 1;
            
        while(lp<=rp){
            
            max_left = Math.max(max_left,height[lp]);
            max_right = Math.max(max_right, height[rp]);
            
            if(max_left < max_right) {
                 res += max_left - height[lp];
                 lp++;
            }
            else {
                res += max_right - height[rp];
                rp--;
            }
               
        }
        
        return res;
    }
}

Agnibha Chandra

Approach 2:

Java

class Solution {
    public int trap(int[] height) {
        if(height.length < 3) return 0;
        int lm = height[0];
        int rm = height[height.length - 1];
        int lmax[] = new int[height.length -1];
        int rmax[] = new int[height.length -1]; 
        for(int i = 1; i< height.length-1; i++){
            lm = Math.max(lm,height[i-1]);
            lmax[i] = lm;
        }
        for(int j = height.length - 2; j > 0; j--) {
            rm = Math.max(rm,height[j+1]);
            rmax[j] = rm;
        }
        int water = 0;
        for(int i = 1; i < height.length -1 ; i++)
        {
            water += Math.max((Math.min(lmax[i],rmax[i]) - height[i]),0);
        }
        return water;
        
    }
}

Agnibha Chandra