Last Updated: 17 Nov, 2020
Container with Maximum Water
Easy
Asked in companies
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.
Example:
Consider 'ARR'= {1,8,6,2,5,4,8,3,7} then the vertical lines are represented by the above image. The blue section denotes the maximum water than a container can contain.
Input Format:
The first line contains a single integer ‘T’ denoting the number of test cases.
The first line of each test case contains a single integer ‘N’ denoting the number of elements in the array/list.
The second line of each test case contains ‘N’ single space-separated integers denoting the elements of the array/list.
Output Format:
For each test case, return a single integer which denotes the maximum area of the container.
Note:
You don’t need to print the output, It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
2 <= N <= 5000
1 <= ARR[i] <= 10^5
Where 'ARR[i]' denotes the elements of the given array/list.
Time limit: 1 sec
Approaches
The idea is to try all possible pairs as the sides of the container and then calculate the maximum area out of all the pairs.
The steps are as follows:
- We will iterate through the array/list and pivot each element as the left side of the container. Let’s say this element is at the 'i’th index.
- And for the right side of the container start exploring from the next index of ‘i’ and pivot each element as the right side of the container. Let’s call this index ‘j’.
- The area of the container with the sides as ‘ARR[i]’ and ‘ARR[j]’ will be (j - i) * (min('ARR[i]', 'ARR[j]').
- This way, we will explore all possible containers and then take the maximum area out of all the containers.
- Return the maximum area of out of all possible containers.
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:
- 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.
- 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]’).
- If the area is greater than the value of ‘maxArea’, then update 'maxArea' to the current area.
- 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.
- Return the value of 'maxArea'.
Similar problems