Easy Concise Java O(N) Solution with Proof and Explanation


  • 141
    M

    AKA, the general idea to find some max is to go through all cases where max value can possibly occur and keep updating the max value. The efficiency of the scan depends on the size of cases you plan to scan.
    To increase efficiency, all we need to do is to find a smart way of scan to cut off the useless cases and meanwhile 100% guarantee the max value can be reached through the rest of cases.

    In this problem, the smart scan way is to set two pointers initialized at both ends of the array. Every time move the smaller value pointer to inner array. Then after the two pointers meet, all possible max cases have been scanned and the max situation is 100% reached somewhere in the scan. Following is a brief prove of this.

    Given a1,a2,a3.....an as input array. Lets assume a10 and a20 are the max area situation. We need to prove that a10 can be reached by left pointer and during the time left pointer stays at a10, a20 can be reached by right pointer. That is to say, the core problem is to prove: when left pointer is at a10 and right pointer is at a21, the next move must be right pointer to a20.

    Since we are always moving the pointer with the smaller value, i.e. if a10 > a21, we should move pointer at a21 to a20, as we hope. Why a10 >a21? Because if a21>a10, then area of a10 and a20 must be less than area of a10 and a21. Because the area of a10 and a21 is at least height[a10] * (21-10) while the area of a10 and a20 is at most height[a10] * (20-10). So there is a contradiction of assumption a10 and a20 has the max area. So, a10 must be greater than a21, then next move a21 has to be move to a20. The max cases must be reached.

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

  • 0
    V

    Very good explanation, thanks!


  • 2
    T

    Can you please explain how you find out this solution?


  • 0
    W

    nice solution!


  • 3
    M

    Think of possible solutions, make a guess, math proof. It's kind of typical way to find out an algorithm. I recommend you a website about finding out brilliant algorithms: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/


  • 0
    H

    Nice proof!!!!


  • 0
    E

    yeah,I get the same solution .

    public class Solution {
    public int maxArea(int[] height) {
        if(height==null || height.length<2){
            return 0;
        }
        int result = 0;
        int left =0,right=height.length-1,temp=0;
        while(left<right){
            temp = (Math.min(height[left],height[right]))*(right-left);
            if(temp>result){
                result = temp;
            }
            if(height[left]>height[right]){
                right--;
            }else{
                left++;
            }
        }
        return result;
    }
    

    }

    for every loop,(right-left) must be smaller,so we can keep the max of (height[left],height[right]) for the next loop,we get the max in the end!


  • 0
    Z

    Thanks! It‘s easier to understand than the "Simple and fast C++/C with explanation".
    And "Yet another way to see what happens in the O(n) algorithm" is also related to this solution.


  • 5
    S

    Why this solution is giving TLE?

    public int maxArea(int[] height) {
        if(height == null || height.length < 2) return 0;
        int left = 0;
        int right = height.length-1;
        int ans = Integer.MIN_VALUE;
        while(left < right){
            ans = Math.max(ans, Math.min(height[left], height[right])*(right-left));
            if(height[left] < height[right]){
                left++;
            }else if(height[left] == height[right]){
                right--;
                left++;
            }else{
                right--;
            }
        }
        return ans;
    }

  • 0
    L

    Really good solution!!! Thx!!


  • 1
    D

    Hello @saayaa , I just tried your code and I don't see any TLE.
    @saayaa said in Easy Concise Java O(N) Solution with Proof and Explanation:

    public int maxArea(int[] height) {
    if(height == null || height.length < 2) return 0;
    int left = 0;
    int right = height.length-1;
    int ans = Integer.MIN_VALUE;
    while(left < right){
    ans = Math.max(ans, Math.min(height[left], height[right])*(right-left));
    if(height[left] < height[right]){
    left++;
    }else if(height[left] == height[right]){
    right--;
    left++;
    }else{
    right--;
    }
    }
    return ans;
    }


  • 0
    J

    brilliant solution! Thx 4 the explanation!


  • 0
    L

    well done!! nice work


  • 0
    K

    with this input [ 6, 2, 1, 4 ] algorithm is giving the output as 12.
    but there is no common are of 12..


  • 0
    X

    @saayaa change"ans = Math.max(ans, Math.min(height[left], height[right])*(right-left));" to
    "ans = Math.max(ans, Math.min(height[left], height[right])
    *(right-left));"
    and then it is accepted. I meet the same problem.


  • 0
    J

    Awesome solution, I think it can be improved a little bit
    Since we move the smaller value pointer to the inner array, instead of moving the pointer to the next value, we can save some time by moving the pointer to the next larger value because smaller height must result in a smaller area which is not a good candidate for the maximum area

    public int maxArea(int[] height) {
        int left=0,right=height.length-1,max=0;
        while(left<right){
            max=Math.max(max,Math.min(height[left],height[right])*(right-left));
            if(height[left]<height[right]){
                int preleft=height[left];
                while(height[left]<=preleft && left<right){
                    left++;
                }
            }
            else{
                int preright=height[right];
                while(height[right]<=preright && left<right){
                    right--;
                }
            }
        }
        return max;
    }
    

  • 0
    P

    Nice proof, thank you!


  • 0
    R

    @keep_coding There is, (last element index-1st element index) * (min(height at those indices))


  • 0
    G

    @mo10 Something is interesting for the code:

    maxArea = Math.max(maxArea, Math.min(height[left], height[right])* (right - left));
    

    When I write it as:

    maxArea = Math.max(maxArea, (right - left)*Math.min(height[left], height[right]));
    

    The feedback is always Time Limit.
    What is the difference?


  • 0
    D

    what if the height[left] == height[right], if you don't care about this case, maybe it will miss the maximun value


Log in to reply
 

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