Given n non-negative integers a₁, a₂, …, a_n , where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7] 
Output: 49

class Solution {
    public int maxArea(int[] height) {
        
    }
}

Idea - 1

We try all of the possible pairs of bars for the container. Time complexity and space complexity .

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        
        for(int i = 0; i < height.length-1; ++i)
        {
            for(int j = i+1; j < height.length; ++j)
            {
                int curr = Math.min(height[i], height[j])*(j-i);
                max = Math.max(curr, max);
            }
        }
        
        return max;
    }
}


Runtime: 206 ms, faster than 20.38% of Java online submissions for Container With Most Water.
Memory Usage: 41.3 MB, less than 5.05% of Java online submissions for Container With Most Water.

Idea - 2

We start at two ends because that maximize width. The minimum of the two bars would define the height of the container - this area is best possible for the shorter container. So we move past the shorter. Time and space .

class Solution {
    public int maxArea(int[] height) {
        int i = 0, j = height.length-1;
        int max = 0;
        
        while(i < j)
        {
            int w = j-i;
            int h = Math.min(height[i], height[j]);
            
            max = Math.max(max, w*h);
            
            if(height[i] == h)
            {
                ++i;
            }
            else
            {
                --j;
            }
        }
        
        return max;
    }
}


Runtime: 2 ms, faster than 97.80% of Java online submissions for Container With Most Water.
Memory Usage: 40.6 MB, less than 22.88% of Java online submissions for Container With Most Water.