O(n) Java Solution - Two Pointers


  • 19
       public int maxArea(int[] height) {
    		int maxWater=0, left=0, right=height.length-1;
    		while(left<right) {
    			maxWater = Math.max(maxWater,(right-left)*Math.min(height[left], height[right]));
    			if(height[left]<height[right]) left++;
    			else right--;
    		}
    		return maxWater;
    	}
    
    1. Start with pointer left=0 and pointer right=length-1
    2. The max water is limited by the pointer with smaller height
    3. When moving a pointer, the width of the area decrease
    4. If we move the pointer with higher height, we will never get a
      greater area, the max height will be at most the one of the pointer with smaller height.
    5. So we need to move the pointer with smaller height to have a chance to get higher height at the next step.

  • 0
    F

    Nice answer and clear explanation! Thanks!


  • -2
    J

    I think it wil be faster

    // if(height[left]<height[right])
            //     left++;
            // else 
            //     right--;
            if(height[left]<height[right]){
                lastIndex = left;
                left++;
                while(left<right){
                    if(height[lastIndex]>height[left])
                        left++;
                    else
                        break;
                }
            }
            else{
                lastIndex = right;
                right--;
                while(left<right){
                    if(height[lastIndex]>height[right])
                        right--;
                    else
                        break;
                }
                
            }// if(height[left]<height[right])
            //     left++;
            // else 
            //     right--;
            if(height[left]<height[right]){
                lastIndex = left;
                left++;
                while(left<right){
                    if(height[lastIndex]>height[left])
                        left++;
                    else
                        break;
                }
            }
            else{
                lastIndex = right;
                right--;
                while(left<right){
                    if(height[lastIndex]>height[right])
                        right--;
                    else
                        break;
                }
                
            }

  • 0
    A

    Nice solution. Folllowing change gives a better performance.

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

  • 0

    Improved it a bit further. Java runtimes jump all over the place, though, huge differences even when submitting the exact same program several times.

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

Log in to reply
 

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