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;
}