Java solution that beats 90% with explanation


  • 1
    L

    The core idea behind this algorithm is to realize that any tower will not hold water if there are no left and right towers bigger than itself. Also, another tricky part is to hold on to calculation as soon as you find a bigger tower on both left and right. It is because you should rather wait to get rather the biggest towers on both left and right as the water will be held if we have towers in increasing order. So we reach to the max tower for each index and then start our calculation. To give an example: let us say, here is our array: 5,1,3,4

    1. Find the left max for each position. -1,5,5,5
    2. Find the right max for each position: 4,4,4,-1

    You can use -1 or any identifier to mark start or end. Now the trapped water will be the positive difference of min of right or left for each position - height of the container at index. In our case it will be 0 + (4-1) + (4-3) + 0 = 4

      public int trap(int[] height) {
            if(height==null || height.length==0) {
                return 0;
            }
            
            int[] leftmax = new int[height.length];
            int[] rightmax = new int[height.length];
            int left=-1;//all positive numbers.
            for(int i=0;i<height.length;i++) {
                leftmax[i]=left;
                left=Math.max(left,height[i]);
            }
            int right=-1;
            for(int i=height.length-1;i>=0;i--) {
                rightmax[i]=right;
                right=Math.max(right,height[i]);
            }
    
            int water=0;
            for(int i=0;i<height.length;i++) {
                int min = Math.min(leftmax[i],rightmax[i]);
                if(min-height[i]>0) {
                    water += min-height[i];
                }
            }
            
            return water;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.