A O(n) solution


  • 0
    A

    I tried nLog(n) and passed. but this is a O(n) solution.

    /**
     * Solution II: Passed, O(n)
     * From left to right, fill water to the max height so far.
     * From right to left, fill water to the max height so far.
     * Iterate through, for each position, pick the min of 2 heights.
     * Calculate volume.
     * 
     * We can view this as sort of "greedy": 
     * 1. always fill water to the max from 1 side.
     * 2. but have to verify if we will find an equal or higher edge on the other side.
     * 3. thus we go directions and pick the smaller height at each index.
     */
    public int trap(int[] A) {
        // edge case
    	if (A == null || A.length <= 1)
    		return 0;
    	
    	int max = 0;
    	int[] heights1 = new int[A.length];
    	for (int i = 0; i < A.length; i++) {
    		int curr = A[i];
    		if (curr > max)
    			max = curr;
    		heights1[i] = max;
    	}
    	
    	max = 0;
    	int[] heights2 = new int[A.length];
    	for (int i = A.length - 1; i >= 0; i--) {
    		int curr = A[i];
    		if (curr > max)
    			max = curr;
    		heights2[i] = max;
    	}
    	
    	int volume = 0;
    	for (int i = 0; i < A.length; i++)
    		volume += Math.min(heights1[i], heights2[i]) - A[i];
    	
    	return volume;
    }

  • 0
    A

    All right, this O(n) solution is simpler, it only requires 1 iteration.

    /**
     * O(n)
     * use 2 pointers from left and right, moving toward either other.
     * assume left < right;
     *  keep moving left and fill the gaps,
     *  height of water = max height so far,
     *  stop when encounter a left > right.
     * do the same for right, until encounter a right > left.
     * switch between left and right, hold the larger one and move the 
     * smaller one.
     */
    public int trap(int[] A) {
        // edge case
    	if (A == null || A.length <= 1)
    		return 0;
    	
    	int[] heights = new int[A.length];
    	int left = 0, right = A.length - 1;
    	int leftMax = 0, rightMax = 0;
    	while (left <= right) {
    		int leftHeight = A[left];
    		int rightHeight = A[right];
    	    if (leftHeight <= rightHeight) {
    	        if (leftHeight > leftMax)
    	            leftMax = leftHeight;
    	        // right is higher, so the height is purely
    	        // determined by the max height on left.
                heights[left] = leftMax;
                left++;
    	    } else {
    	        if (rightHeight > rightMax)
    	            rightMax = rightHeight;
                heights[right] = rightMax;
                right--;
    	    }
    	}
    	
    	int volume = 0;
    	for (int i = 0; i < A.length; i++)
            volume += heights[i] - A[i];
    	
    	return volume;
    }

  • 0
    S

    Here is what I thought of... it does not required creating a new array and time complexity is O(n)

    int trap(int A[], int n) {
    if( n==0 || n==1 ){
    return 0;
    }

    	int maxID =0, max=0;
    	for( int i=0; i<n ; i++ ){
    		if (max < A[i]) {
    			max = A[i];
    			maxID = i;
    		}
    	}
    	
    	int totalWater = 0;
    	int currentLevel = A[0];
    	int currentStorage = 0;
    	
    	for (int i=0 ; i<maxID; i++ ){
    		if ( currentLevel >= A[i] ){
    			currentStorage = currentStorage + currentLevel - A[i];
    		}
    		else {
    			totalWater = totalWater + currentStorage;
    			currentStorage = 0;
    			currentLevel = A[i];
    		}
    	}
    	totalWater = totalWater + currentStorage;
    	
    	currentLevel = A[n-1];
    	currentStorage = 0;
    	
    	for (int i=n-1 ; i>maxID; i-- ){
    		if ( currentLevel >= A[i] ){
    			currentStorage = currentStorage + currentLevel - A[i];
    		}
    		else {
    			totalWater = totalWater + currentStorage;
    			currentStorage = 0;
    			currentLevel = A[i];
    		}
    	}
    	totalWater = totalWater + currentStorage;
    	
    	return totalWater;
    }   
    

Log in to reply
 

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