Container with most water

Question

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

Input: height = [1,8,6,2,5,4,8,3,7]

Output: 49

Explanation: 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.

Now, let's see how can we solve this problem.

Solution

Brute Force Approach

Here, we will try all the combination starting from first index to the last one.

So we will try combinations like : (1, 1), (1, 2).. (1, n) to (n, 1).. (n, n)

and we will keep a value to check the max area we are getting each time. By the end of the iteration we will get the max area which will be the answer.

Time complexity : O(n ^ 2)

Code:

Here, a JAVA implementation by the Brute Force approach.

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

Now let us check if we can bring down the time complexity to Linear time

Enhanced solution

We will try to find an intuition over here:

The max area for any rectangle would be one where width is max. So, considering that both the ends have max height, the highest area we will get is considering the first and last values.

Therefore, we will initiate two pointers, left and right like below:

Now, we will calculate the area as length X width. Here length is the min height between two i.e, 1 and width is distance between two pointer i.e, 8. So total area is 8.

Next, we will see among the two heights, left and right, which is lower.

We will then update the pointer for the pointer whose value is lower.

Here, left has lower value, so we will update the left as left + 1 and keep right as it is.

Here again we will calculate the area. This time L = 7 and width = 7. Hence area is 7X7 = 49

Comparing this to previous value of 8, since 49 is higher we will consider this as answer.

Now among the two pointers, here right has lower value so, we will update the rigth pointer as below:

Here, area = 3 X 6 = 18 which is lower than max we got till now. Hence we will ignore and move forward as below:

We will carry on this process, calculating area each time and updating the pointers till left is less than right pointer.

As soon as left > right, we will break (Similar to Binary Search 🔍)

At the end we will be able to find the max area which will be 49 in this case.

Let's see the JAVA implementation:

public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

        while (left < right) {
            maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left));
            if (height[left] < height[right]) {
                left = left + 1;
            } else {
                right = right - 1;
            }
        }
        return maxArea;
    }

Thus we were able to enhance the solution to a time complexity of O(n) which is way better than the Brute force.


Hope you liked it ! I would love to know if you have any other better approach in mind.

Tirthankar Kundu

Tirthankar Kundu