Container with most water
Given a sequence of ‘N’ space-separated non-negative integers A[1],A[2],A[3],......A[i]…...A[n]. Where each number of the sequence represents the height of the line drawn at point 'i'. Hence on the cartesian plane, each line is drawn from coordinate ('i',0) to coordinate ('i', 'A[i]'), here ‘i’ ranges from 1 to ‘N’. Find two lines, which, together with the x-axis forms a container, such that the container contains the most area of water.

Note :

1. You can not slant the container i.e. the height of the water is equal to the minimum height of the two lines which define the container. 2. Do not print anything, you just need to return the area of the container with maximum water.

Example

For the above Diagram, the first red marked line is formed between coordinates (2,0) and (2,10), and the second red-marked line is formed between coordinates (5,0) and (5,9). The area of water contained between these two lines is (height* width) = (5-2)* 9 = 27, which is the maximum area contained between any two lines present on the plane. So in this case, we will return 3* 9=27.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases. The next ‘2*T’ lines represent the ‘T’ test cases. The first line of each test case contains the number of elements in the sequence. The second line of each test case contains ‘n’ space-separated integers which is the given sequence.

Output format :

For every test case return the area of the container which can hold the maximum amount of water using any pair of lines from the given sequence.

Constraints:

1

Question

Container with most water

Given a sequence of ‘N’ space-separated non-negative integers A[1],A[2],A[3],......A[i]…...A[n]. Where each number of the sequence represents the height of the line drawn at point 'i'. Hence on the cartesian plane, each line is drawn from coordinate ('i',0) to coordinate ('i', 'A[i]'), here ‘i’ ranges from 1 to ‘N’. Find two lines, which, together with the x-axis forms a container, such that the container contains the most area of water.

Note :

1. You can not slant the container i.e. the height of the water is equal to the minimum height of the two lines which define the container.

2. Do not print anything, you just need to return the area of the container with maximum water.

Example

water-diagram

For the above Diagram, the first red marked line is formed between coordinates (2,0) and (2,10), and the second red-marked line is formed between coordinates (5,0) and (5,9). The area of water contained between these two lines is (height* width) = (5-2)* 9 = 27, which is the maximum area contained between any two lines present on the plane. So in this case, we will return 3* 9=27.

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The next ‘2*T’ lines represent the ‘T’ test cases.

The first line of each test case contains the number of elements in the sequence.

The second line of each test case contains ‘n’ space-separated integers which is the given sequence.

Output format :

For every test case return the area of the container which can hold the maximum amount of water using any pair of lines from the given sequence.

Constraints:

1 <= T <= 50
0 <= N <= 10^4
1 <= A[i] <= 10^5

Time Limit: 1 sec

Accepted Answer

Brute Force Approach

Since we need to find the container with most water, let us try to find all possible containers and choose the one which has the maximum area.

So how can we find the area of all possible containers?

We can, for each line with the position ‘i’ find another line ‘j’ such that ‘j’ > ‘i’ and find the amount of water contained i.e (‘j’-’i’)*min('A[i]', ‘A[j]’) where ‘A[i]’ and ‘A[j]’ represents the height of the lines at index ‘i’ and ‘j’ respectively.

We can do this in the following way:

Take a variable ‘GLOBAL_MAX' to store the overall maximum area and initialize it to some very small value (eg -1).
Let ‘N’ be the number of lines in the sequence.

Let ‘HEIGHT[i]’ be the height of the first line of any container. Then for each ‘i’ we find ‘HEIGHT[j]’ where ‘i’
In the end, we return the value of ‘GLOBAL_MAX’.

Space Complexity: O(1)Explanation:

O(1),

We are using constant space.

Time Complexity: O(n^2)Explanation:

O(N^2), Where ‘N’ denotes the number of elements in the given sequence.

For each starting height, we calculated the area for the container. This is done for all ‘N’ lines in the container and in the worst case, this is done ‘N’ times. Hence the complexity is of order O(N^2).

Accepted Answer

Two Pointers Approach

We know that area=width*length. So increasing the length of line or width between two lines will increase the area.
If we start with the two extremes of the sequence, i.e the first and last line, we can achieve maximum width.
But this does not ensure maximum area as it is possible that some pair of lines with a lesser width and much greater length than the extreme lengths can have a greater area.
So this is obvious that if we decrease the width we need to find such a pair of lines that the length of the shorter line is more than the maximum of the previous pair of lines.
Keeping all that in mind we can use the following strategy to find the maximum area:
Let the ‘i-th’ line be used to denote the first line of the container and ‘j-th’ line be used to denote the second line and ‘N’ be the number of lines in the sequence.
We start from the widest container i.e ‘i=1’ and ‘j=N’. Now for a better answer with a lesser width, it is necessary that the height is higher than the current heights.
Now discard the height which is lower among the two heights ‘i’ and ‘j’ because having a greater height will allow us to have a better answer. If it is ‘i’ move the ‘i’ pointer to the right and if it is ‘j’ move it to the left.
Calculate the area of the new container formed and update the maximum area if the newly found area is greater than the previous maximum area.
Do this until ‘i’ is less than ‘j’.
In the end, we return the maximum area found at the end of the loop.

Space Complexity: O(1)Explanation:

O(1),

We are using constant space.

Time Complexity: O(n)Explanation:

O(N), Where ‘N’ denotes the number of elements in the given sequence.

Since we traverse the sequence once to find the container with maximum water, the time complexity is the order of O(‘N’).

Python (3.5)

'''

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

    Where 'N' is the number of elements in the sequence

'''

def maxArea(height):

    n = len(height)
    # Variable to store overall maximum area.
    globalArea = -1

    startIndex = 0
    endIndex = n-1

    while startIndex < endIndex:
        minHeight = min(height[startIndex], height[endIndex])
        globalArea = max(globalArea, (endIndex-startIndex)*minHeight)

        # Until we find some greater height from starting index.
        if height[startIndex] <= minHeight:
            startIndex += 1
        # Until we find some greater height from ending index.
        else:
            endIndex -= 1

    return globalArea

Note :

Example

Input format :

Output format :

Constraints:

Top Paytm Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Paytm Software Developer