Simple O(n) time O(1) solution in Java


  • 8
    Z

    The idea is that a container to hold water can only be formed by two two heights with the lowest height as the height of the container. So, if we start from two numbers farthest apart in length (i.e. first and last element) then we have maximum width rectangle. Now, we can move to shorter height only to left or right to maximize the total area.

    public class Solution {
        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;  
        }
    }

  • 0
    O

    Same approach but a bit more compact.

    public class Solution {
        public int maxArea(int[] height) {
            int result = 0;
            for (int a = 0, b = height.length - 1; a < b;) {
                result = Math.max(result, Math.min(height[a], height[b]) * (b - a));
                if (height[a] < height[b]) a++; else b--;
            }
            return result;
        }
    }

Log in to reply
 

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