Water tank with largest capacity- Coding question

Problem Statement:

You are given a set of vertical lines at equal interval of distances, two of which combined can make up walls of cemented water tank. Find the two walls which form tank of largest capacity.

Input format :

Vector array whose each element denoting height of the walls and difference between the indices depict width of the tank.

Output format :

Maximum capacity of water tank

Sample Input 1:

[1,8,6,2,5,4,8,3,7]

Sample Output 1:

49

Sample Input 2:

[1,3,2]

Sample Output 2:

2

Explanation of output:

We are given a set of heights of walls in form of array.

The distance between these walls is uniform (1 unit). Largest area that can be formed by joining any of these two heights.

We can calculate the area using the formula,

Area = minimum{height 1, height 2} * width

Approach 1(Naive):

The naive approach to this problem is to check every possible combination of the given heights. It goes by:-

1. Using two loops, fix the the outer loop and move the inner loop to check every possible combination of two heights in the given array.
2. Outer loop runs from 0 to n-1 and inner loop runs from outer Loop Index + 1 to n.
3. For each iteration of the inner loop you will get a pair of heights. Check if the area formed using this pair of heights is greater than the max area so far.
4. If yes update the result, else continue to check the next pair.
5. Repeat step 1–4 for all possible pair of heights.
6. Finally return the maximum area obtained as the result.

Time Complexity: O(n²)

Above approach has a higher time complexity and will exceed the time limit for larger test cases.

Code(for approach 1):

Approach 2(two pointer):

To use this approach, first we need to notice a pattern. For [1,8,6,2,5,4,8,3,7] to be given array, if we start with first and last heights and move inwards i.e. (1,7), (1,3), (1,8), (1,4) and so on, you can see that you get no benefit by using combinations (1,3), (1,8), (1,4) so on after (1,7) to calculate area, as the minimum height obtained by using any of these combinations remains same. This is so because in all cases 2nd height is greater than the 1st height (height1= 1, which is same for all the pairs), and since we take the minimum of 1st and 2nd heights while calculating the area, we always end up with 1 as the result(for minimum height) for all the above combinations. This is true for all such cases where for a set of combinations one of the heights is same and it is smaller than the other height in all pairs. Also the width keeps decreasing as we move inwards, for (1,7) width is 8, for (1,3) width is 7, for (1,8) width is 6 and so on. Therefore the area also will decrease.

We can use this to our advantage to solve this problem in linear time.

Time complexity=O(n)

Code(for approach 2):

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.