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.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Strings Quiz

ACNA Explained: The 6 Key Capabilities behind Cloud-Native

Software Engineering is much more than just building APIs

{UPDATE} Activo!

ARMing Kubernetes with OpenEBS #1

Alibaba Cloud ACK Pro and ACK@Edge: Cloud-Native Evolution for Enterprises

How to add/publish a jupyter notebook to Gist-github

My questions to the developers in the job interview

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

Class Quiz

“Delete and Earn” problem using Dynamic Programming

LeetCode 253 — Meeting Rooms 2

Scattered Rice Coding Question