In this Leetcode Trapping Rain Water problem solution, we have 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.

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