Anyone who has a O(N) algorithm ?


  • 24
    Y

    anyone who has a O(N) algorithm ?

    I am using the following code but the time exceeds the limit for the extreme case (ascending sequece) , so I added some special code to handle the extreme case to get a pass. Anyone who has better solution?

    	public  int maxArea1(int[] height){
    	if ( (height == null) || (height.length <= 1) )
    		return 0 ;
    	int result = 0 ;
    	ArrayList<Integer> seq = new ArrayList<Integer>();
    	seq.add(new Integer(0));
    	for (int i = 1 ; i < height.length; i++){
    		for ( Integer idx : seq ){
    			int ht = height[i] > height[idx.intValue()] ? height[idx.intValue()] : height[i] ;
    			int area = (i - idx.intValue()) * ht ;
    			if ( area > result ) result = area ;
    		}
    		int lastIdx = seq.get(seq.size() - 1).intValue();
    		if ( height[i] > height[lastIdx]){
    			seq.add(new Integer(i)) ;
    		}
    	}		
    	return result ;
    	
    }

  • 315
    S

    Here is a solution by n00tc0d3r from old discuss. Thanks n00tc0d3r.

    public int maxArea(int[] height) {  
       int len = height.length, low = 0, high = len -1 ;  
       int maxArea = 0;  
       while (low < high) {  
         maxArea = Math.max(maxArea, (high - low) * Math.min(height[low], height[high]));  
         if (height[low] < height[high]) {  
           low++;  
         } else {  
           high--;  
         }  
       }  
       return maxArea;  
     }
    

    Here is the proof.
    Proved by contradiction:

    Suppose the returned result is not the optimal solution. Then there must exist an optimal solution, say a container with a_ol and a_or (left and right respectively), such that it has a greater volume than the one we got. Since our algorithm stops only if the two pointers meet. So, we must have visited one of them but not the other. WLOG, let's say we visited a_ol but not a_or. When a pointer stops at a_ol, it won't move until

    • The other pointer also points to a_ol.
      In this case, iteration ends. But the other pointer must have visited a_or on its way from right end to a_ol. Contradiction to our assumption that we didn't visit a_or.

    • The other pointer arrives at a value, say a_rr, that is greater than a_ol before it reaches a_or.
      In this case, we does move a_ol. But notice that the volume of a_ol and a_rr is already greater than a_ol and a_or (as it is wider and heigher), which means that a_ol and a_or is not the optimal solution -- Contradiction!

    Both cases arrive at a contradiction.


  • 75
    W

    Here is a simple proof for the solution.
    Use v[low, high] indicates the volume of container with low and high. suppose height[low] < height[high], then we move low to low+1, that means we ingored v[low, high-1],v[low, high-2],etc, if this is safe, then the algorithm is right, and it's obvious that v[low, high-1],high[low, high-2]...... can't be larger than v[low, high] since its width can't be larger than high-low, and its height is limited by height[low].


  • 1
    Y

    this proof is not perfect. when height[low] < height[high], then we move to low+1.It is true that we can ignore v[low, high-1], v[low,high-2]...safely, but we can not ignore v[low+1, n-1], v[low+1, n-2]...v[low+1, high+1], so you will have to move high back to n-1, this again makes the algorithm O(n^2)


  • 0
    L

    The proof is correct, and your comment does not seem related to the proof. If you think you have found a mistake in the proof, you can either point exactly to the incorrect statement of the proof, or give a counter example. Your comment seems like you have a O(n^2) algorithm and you're trying to prove its correctness.


  • 2
    R

    Consider it as a dynamic programming problem and you get the clear proof.

    assume h[from] < h[to], then the largest volume we can get, using 'from' as one side, is (to - from + 1) * h[from]. then we can say:

    opt[from][to] = max(opt[from + 1][to], (to - from + 1) * h[from]).


  • 0
    F

    The question seems to be easier than what I expected. If your algorithm, the height is decided only by two end points, Math.min(height[low], height[high]). How about another variation, the height is decided by the min value in internal [low, height], which makes more sense since the water level should be decided the shorted. For example, considering the array {4, 2, 1, 3}, length = 3, but the water volume should be 3 * 1 (1 is the minimal in the interval), instead of 3 * 3 (3 is the min of two end points).

    which program is harder? the original one or the variation? Thanks


  • 0
    G

    Excellent greedy algorithm


  • 0
    R

    In general it'd be really helpful to include pseudo-code and/or complexity of your solutions, rather than pasting code.

    This seems like a standard DP problem to me. Every cell i,j in the matrix will hold the min height.
    Pretty straight-forward. down side is O(n^2) time and space complexity


  • 0
    X
    This post is deleted!

  • 0
    U

    This greedy search can be improved by dealing with special cases where height is 0 or not in sorted order so that some area calculation can be skipped. (396 ms vs 452ms)

    class Solution:
        # @return an integer
        def maxArea(self, height):
            a, b = 0, len(height)-1
            most = 0
            while a < b:
                if not height[a]:
                    a += 1
                elif not height[b]:
                    b -= 1
                elif height[a] < height[b]:
                    most = max(most, height[a]*(b-a))
                    pre = height[a]
                    while a < b and height[a] <= pre:
                        a += 1
                else:
                    most = max(most, height[b]*(b-a))
                    pre = height[b]
                    while a < b and height[b] <= pre:
                        b -= 1
            return most

  • 0
    Y

    Proof is correct. As Buckets effect reveals, the capacity of a bucket depends on the shortest board, so , we HAVE to move the shortest side.


  • 0
    Z

    My solution is similar to this. Only, mine doesn't calculate and compare the new area each step, instead, it only does that when the new height[low]/height[high] is bigger than last time. the pseudo-code is:

        l := low + 1        
        h := high - 1        
        ...        
        (in the while loop:)        
        if height[low] < height[high]:          
               while height[l] <= height[low]:        
                      l++        
               low := l        
               l++
        else:          
               while height[h] <= height[high]:        
                      h--        
               high := h        
               h--

  • 1
    S

    In addition to wangjie's note. It looks like the comment " it's obvious that v[low, high-1],high[low, high-2]...... can't be larger than v[low, high] " is not self explanatory enough. Let me add some note to put it in this way.

    If height[low] < height[high], which means the limit will be height[low]. In this case if we move the higher end, height[high], we may end up with two situations, height[high-1] > height[low]. and height[high-1] < hight[low].. For the former one, it does not change a thing as the limit is still heigh[low], but it shrinks the length on x-axis by 1. For the latter case, it not only reduces the limit height on y-axis, but also reduced the length on x-axis. Both cases will yield smaller area. That is why, moving the shorter end will be safe.

    So I think this solution has an essence of moving the lower side bound of the container. In this case, it won't miss the biggest area.


  • 5
    R

    Python verson:

    class Solution:
    # @return an integer
    def maxArea(self, height):
        left=0
        right=len(height)-1
        result=0
        while left<right:
            result=max(result,(right-left)*min(height[left],height[right]))
            if  height[left]<height[right]:
                left+=1
            else:
                right-=1
        
        return result

  • 0
    S

    your prove is great.


  • 1
    D
    class Solution {
    public:
        int maxArea(vector<int> &height) {
            int left = 0, right = height.size()-1;
            int vol, maxvol = (right-left)*min(height[left], height[right]);
            int l=left, r=right;
            while(left<right){
                if(height[left] <= height[right]){   // add "=" in consideration of equalization situation
                    while(height[++left]<=height[l] && left < right);   // add "left<right" in case of innecessary visits
                    vol = (right-left)*min(height[left], height[right]);
                    l = left;
                    if(vol>maxvol){
                        maxvol = vol;
                    }
                }
                if(height[left] > height[right]){
                    while(height[--right]<=height[r]);   // here "left<right" is not needed
                    vol = (right-left)*min(height[left], height[right]);
                    r = right;
                    if(vol>maxvol){
                        maxvol = vol;
                    }
                }
            }
            return maxvol;
        }
    };

  • 0
    W

    For the 2nd case that we will move aol, the volume is larger than the optimal one is because the two height is same(at most height of aol) but aol & arr is wider than the optimal solution.


  • 0
    W

    so smart,so awesome


  • 0
    L

    thanks stanley!


Log in to reply
 

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