Java Simple O(N) solution


  • 0
    public int maxArea(int[] height) {
        if (height.length == 0)
            return 0;
            
        int overAllMax = Integer.MIN_VALUE;
        
        for (int i=0,j=height.length-1;i<j;){
            // calculate the current area;
            int currentArea = Math.abs(i-j) * Math.min(height[i],height[j]);
            // if it is greater than the already greater are then update it
            overAllMax = overAllMax < currentArea ? currentArea : overAllMax;
            
            // change the pointer with respect to their heights
            
            // if the height is lesser
            if (height[i] < height[j]) 
                i++;
            // if it is greater
            else if (height[i] > height[j])
                j--;
            // if the heights are equal
            else{
                i++;
                j--;
            }
        }
        // return the max area
        return overAllMax;
    }

  • 1
    D

    @sati3000mangmail.com Could you kindly explain why this solution could always produce the right answer?


  • 0
    D

  • 0
    S

    @demongaorui Yes. This solution is based on greedy strategy, where I am not able to find one counter example. If the area which I have found hitherto is the maximum then I should search for the next maximum area by moving one step forward from the smaller wall, if both heights are equal then move forward from both the walls. Hope it helps. Please let me know for any further questions.


Log in to reply
 

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