Container with Maximum Water — Asked in Google, Adobe and Facebook Interview

Problem Statement :

You have been given an array/list ‘ARR‘ of length ’N’ consisting of non-negative integers ARR1, ARR2, …, ARRN. The i’th integer denotes a point with coordinates (i, ARR[i]). ’N’ vertical lines are drawn such that the two endpoints of the i’th line are at (i, arr[i]) and (i,0).

Your task is to find two lines, which, together with the x-axis, form a container, such that the container contains the most water. Return the maximum area of the container.

Note:

1. Consider the container to be 2-dimensional for simplicity.

2. For any pair of sides ignore all the lines that lie inside that pair of sides.

3. You are not allowed to slant the container.

Sample Input:

5
2 4 7 1 3

Sample Output:

9

Explanation of given Test Case :

In the first test case, we will get the maximum area if we choose the container coloured blue in the above image. The length of the base of the container is 3, and the height of the container is min(4, 3) which is 3. Thus, the area of the container is 3 * 3 = 9.

Approach :

Two-pointer Approach

The idea is to use the two-pointer technique and greedily select the sides of the container. We know that the area of the container is limited by the height of the shorter side and also by the length of the base of the container, so to maximize the area we can remove the side with a shorter length and choose a side that has a bigger length and at the same time keep the length of the base as large as possible.

The steps are as follows:

1. Take two pointers: the first one pointing to the first element of the array, let’s say ‘i’, and the second pointing to the last element of the array/list, let’s say ‘j’. Also, we will use a variable ‘maxArea’ which will be initialized to 0 to store the maximum area.
2. We will calculate the area of the container by taking the elements of the two pointers as to the sides of the container, and the area will be equal to (‘j’ — ‘i’) * ( min(‘ARR[i]’, ‘ARR[j]’).
3. If the area is greater than the value of ‘maxArea’, then update ‘maxArea’ to the current area.
4. If ‘ARR[i]’ < ‘ARR[j]’ then increment ‘i‘ by 1. Otherwise, decrement ‘j’ by 1. This is the optimal way because the shorter side limits the area of the container so, in order to increase the area, we remove the shorter side and choose another element as the side.
5. Return the value of ‘maxArea’.

Time Complexity: O(N)
Space Complexity: O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.