Trapping Rain Water Problem Solution

Trapping Rain Water Problem: 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.

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.

Trapping Rain Water Problem Solution

Problem Solution In Python

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height: return 0
        
        water, n = 0, len(height)
        max_left, max_right = [None] * n, [None] * n
        max_left[0], max_right[-1] = height[0], height[-1]
        
        for i in range(1, n):
            max_left[i] = max(max_left[i-1], height[i])
            
        for i in range(n-2, 0, -1):
            max_right[i] = max(max_right[i+1], height[i])
            water += min(max_left[i], max_right[i]) - height[i]
            
        return water

Problem Solution In Java

class Solution {
    public int trap(int[] height) {
        int l=0;
        int r=height.length-1;
        while(l<r && height[l]<height[l+1])
            l++;
        while(l<r && height[r]<height[r-1])
            r--;
        int ans=0;
        
        while(l<r){
            int left=height[l];
            int right=height[r];
         if(left<=right){   
            while(l<r && left>=height[l]){
                ans+=left-height[l];
                l++;
            }}
        else{
            while(l<r && right>=height[r]){
                ans+=right-height[r];
                r--;
            }}
        }
        return ans;
    }
}

Problem Solution In C++

int trap(vector<int>& height) {
                
        if (height.size()==0) return 0;

        
        vector<int> heightcopy;
        
        heightcopy=height;
        
        int i,j;
        int Level;
        
        i=0;
        j=height.size()-1;
        Level=0;
        
        while (i<j) {
            if (heightcopy[i]<Level) { heightcopy[i]=Level; i++; }
            else if (heightcopy[i]==Level) i++;
            else if (heightcopy[j]<Level) { heightcopy[j]=Level; j--; }
            else if (heightcopy[j]==Level) j--;
            else if (heightcopy[i]>Level && heightcopy[j]>Level) {
                Level++;

            }
            
        }
            
        int sumTotal = accumulate(heightcopy.begin(), heightcopy.end(), 0);  
        int sumHeight = accumulate(height.begin(),height.end(),0);
        
        
        return sumTotal-sumHeight;
        
    }

Problem Solution In C

int trap(int* height, int heightSize){
    int leftMax=0, rightMax=0, left=0, right=heightSize-1, result=0, max;
    
    while(left < right) {
        if(height[left]>leftMax) leftMax = height[left];
        if(height[right]>rightMax) rightMax = height[right];      
        if(leftMax<rightMax) {
            if((leftMax-height[left]) > 0) result += (leftMax-height[left]); 
            left++;
        } else {
            if((rightMax-height[right]) > 0) result += (rightMax-height[right]);
            right--;
        }
    }
    
    return result;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment