Arrays - Container with Most Water

Question: Given an array of positive numbers where each number represent the height of a vertical line on a chart. Find two lines which together with the x-axis forms a container that would hold greatest amount of water. what will be the output which is max area of container formed by vertical lines.

input [8, 2, 1, 5, 6, 9]
output 40                     

Constraints need to ask because solution may change according to given constraints

Question: Does the thickness of lines affect the are?
Answer: No

Question: Sides of graph can be count as wall?
Answer: No

Question: Does a higher line inside our container affect our area?
Answer: No

Question: What will be output for empty array?
Answer: 0

Question: What will be output when only 1 value in array?
Answer: 0

Solution using JAVA language.

Brute Force algorithm - In brute force solution, we try to check each and every possible combination through array. This is a approach in which 2 for loops are involved and polynomial time complexity.

Note: Area = Height * Width 

Formula: min(a,b) * (bi - ai)

* bi = index of b

* ai = index of a

public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{8, 2, 1, 5, 6, 9};
        int result = Solution.getMaxArea(arr);
        System.out.println("Max water above array container can hold - " + result);
    }

    public static int getMaxArea(int[] heights) {
        int maxArea = 0;
        int length = heights.length;
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                int height = Math.min(heights[i], heights[j]);
                int width = j - i;
                int area = height * width;
                maxArea = Math.max(area, maxArea);
            }
        }
        return maxArea;
    }
}

Output: 40

Time Complexity: O(N2)

Space Complexity: O(1)

Solution using JAVA language.

Optimal Solution - Above solution works well but that is not the efficient solution because it has polynomial time complexity. So, we will try to reduce the time complexity to linear. First we think about any data structure which can help but this is not the case here, the 2 pointer shifting technique will work here, let's see the solution.

/*

 *  Two pointer shifting technique

 */

public class Solution {
    
    public static int getMaxArea(int[] heights) {
        int length = heights.length;
        int p1 = 0, p2 = length - 1, maxArea = 0;
        while (p1 < p2) {
            int height = Math.min(heights[p1], heights[p2]);
            int width = p2 - p1;
            int area = height * width;
            maxArea = Math.max(area, maxArea);
            if (heights[p1] < heights[p2]) {
                p1++;
            } else {
                p2--;
            }
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{8, 2, 1, 5, 6, 9};
        int result = Solution.getMaxArea(arr);
        System.out.println("Max water above array container can hold - " + result);
    }

}

Output: 40

Time Complexity: O(N)

Space Complexity: O(1)

Note: Find Question at Leetcode