Simple Java Solution O(n)


  • 0
    public static int trap(int[] A) {
    	if(A==null || A.length<=1) return 0;
    	int lb[] = new int[A.length]; int rb[] = new int[A.length];
    	int maxFromLeft = 0; int maxFromRight = 0; int trappedWater = 0;
    	for(int i=0;i<A.length;i++) {
    		if(A[i]>maxFromLeft) maxFromLeft = A[i];
    		if(A[A.length-1-i]>maxFromRight) maxFromRight = A[A.length-1-i];
    		lb[i] = maxFromLeft; rb[A.length-1-i] = maxFromRight;
    	}
    	for(int i=1;i<A.length-1;i++) {
    		trappedWater = (Math.min(lb[i], rb[i])-A[i]>0)?trappedWater+Math.min(lb[i], rb[i])-A[i]:trappedWater;
    	}
    	return trappedWater;
    }
    
    1. The element lb[i] will store the left bound for the trapped water at position A[i]
    2. The element rb[i] will store the right bound for the trapped water at position A[i]
    3. The trapped water at position A[i] is given by the difference between the smaller bound for position A[i] (Math.min(lb[i], rb[i])), and the height at position A[i] (0 if this difference is negative).

  • 4
    J

    You can in fact improve this version further by reducing the memory needed for the one of the arrays and store the maximum in variable instead.

    public class Solution {
    public int trap(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
    
        final int N = A.length;
        int left = A[0];
    
        final int[] rigth = new int[N];
        rigth[N - 1] = A[N - 1];
        for (int ind = A.length - 2; ind >= 0; ind--) {
            rigth[ind] = Math.max(A[ind], rigth[ind + 1]);
        }
    
        int trap = 0;
        for (int ind = 0; ind < A.length; ind++) {
            left = Math.max(left, A[ind]);
            trap += Math.max(0, Math.min(left, rigth[ind]) - A[ind]);
        }
        return trap;
    }
    

    }


Log in to reply
 

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