Road to Google – Part 2: Container with Most Water

Question:

You are given an array of positive integers where each integer represents the height of a vertical line on a chart.

Find two lines that together with the x-axis form a container that would hold the most significant amount of water.

Return the area of water it would hold.

Explanation:

In this case, you’re given an array of numbers such as:

[1,8,6,2,9,4]

And each number represents the height of vertical bars on a chart as shown in image 01:

In the chart, the highest numbers are 8 and 9.

The question is to find two lines that together can hold the greatest amount of water and return the area of the water that it would hold.

Just like the following image 02:

Area can be found with L(Length) times W(Width):

Formula: Area = L x W

In this case:

Area = 8 x 3

Area = 24

So, 24 is the largest area of water than can be held in two lines in the chart.

Sample 2:

Given the following array:

Now we know that the biggest two numbers are 7 and 9.

From here, let’s figure out the L(length).

The L must be 7, otherwise, if you make the L 9, the water will spill over from the left side.

How do we figure out the width?

Subtract indexes.

In this case, 9’s index is 4 and 7’s is 0

So, 4 – 0 = 4.

The width is 4.

So, the area is 7 * 4 = 28.

As you can see in the chart below, 9 and 7 are 4 units away from each other. And that is the width.

Sample 3

If the array is empty, no container can be formed and the answer is 0.

Also, if the array has 1 number, but still it can’t form a container because it needs at least two of them.

Sample 4

Given the following array:

In this case, there are two possible answers:

6 and 8

or

9 and 8

Let’s figure it out!

6 and 8: They are 5 units apart from each other.

6 * 5 = 30

9 and 8: They are 5 units apart from each other.

8 * 4 = 32

So, the answer is 32.

Thinking time

In the last two_sum question, all we had to do was to find a solution by finding indexes whose corresponding numbers add up to the target number.

In this case, they are 1 and 3.

Once we find it out, we don’t have to worry about the rest anymore.

What needs to be kept in mind is that the container question asks us to figure out the greatest amount of water.

Unlike the previous one, we have to calculate every possible answer and find the one that contains the greatest amount of water.

And reverse kind of question is possible if they ask you to find the least amount of water.

Anyways, the keyword “greatest” is something you need to keep in mind.

Logical and visual explanation:

Take a look at this example which we used in the previous one.

Area is L * W

And L is the lesser of the two.

In the example, let’s use variables for a temporary use case:

a = 7

b = 9

(a, b)

To find out the lesser of the two, use the min function: min(a,b).

ai = a’s index

bi = b’s index

So, the formula is: min(a,b) * (bi – ai)

The program works as shown below:

The first loop

Initialize maxArea = 0

The loop i starts from 7 (let’s make it as a)

And second loop j starts from the unit next to a, which is 1 (j + 1).

min(a,b) * (bi – ai)

min(7,1) * (1 – 0)

1 * 1 = 1

We replace maxArea with 1

The second loop

maxArea = 1

And second loop j starts from the unit next to 1, which is 2 (j + 1).

min(a,b) * (bi – ai)

min(7,2) * (2 – 0)

2 * 2 = 4

We compare the current maxArea, which is 1, to the new maxArea, which is 4.

4 > 1

We replace maxArea with 4

The third loop

maxArea = 4

And third loop j starts from the unit next to 2, which is 3 (j + 1).

min(a,b) * (bi – ai)

min(7,3) * (3 – 0)

3 * 3 = 9

We compare the current maxArea, which is 4, to the new maxArea, which is 9.

9 > 4

We replace maxArea with 9

The fourth loop

maxArea = 9

And fourth loop j starts from the unit next to 3, which is 4 (j + 1).

min(a,b) * (bi – ai)

min(7,9) * (4 – 0)

7 * 4 = 28

We compare the current maxArea, which is 9, to the new maxArea, which is 28.

28 > 9

We replace maxArea with 28

The fifth loop

maxArea = 28

The a is moved to 1

And fifth loop j starts from the unit next to 1, which is 2 (j + 1).

min(a,b) * (bi – ai)

min(1,2) * (2 – 1)

1 * 1 = 1

We compare the current maxArea, which is 28, to the new maxArea, which is 1.

28 > 1

maxArea remeins as 28

The sixth loop

maxArea = 28

And sixth loop j starts from the unit next to 2, which is 3 (j + 1).

min(a,b) * (bi – ai)

min(1,3) * (3 – 1)

1 * 2= 2

We compare the current maxArea, which is 28, to the new maxArea, which is 2.

28 > 2

maxArea remeins as 28

The seventh loop

maxArea = 28

And seventh loop j starts from the unit next to 3, which is 4 (j + 1).

min(a,b) * (bi – ai)

min(1,9) * (4 – 1)

1 * 3= 3

We compare the current maxArea, which is 28, to the new maxArea, which is 2.

28 > 3

maxArea remeins as 28

The eights loop

maxArea = 28

The a is moved to 2

And eighth loop j starts from the unit next to 2, which is 3 (j + 1).

min(a,b) * (bi – ai)

min(2,3) * (3 – 2)

2 * 1 = 1

We compare the current maxArea, which is 28, to the new maxArea, which is 2.

28 > 2

maxArea remeins as 28

the ninth loop

maxArea = 28

And ninth loop j starts from the unit next to 3, which is 4 (j + 1).

min(a,b) * (bi – ai)

min(2,4) * (4 – 2)

2 * 2 = 4

We compare the current maxArea, which is 28, to the new maxArea, which is 4.

28 > 4

maxArea remeins as 28

The tenth loop

maxArea = 28

The a is moved to 3

And tenth loop j starts from the unit next to 3, which is 9 (j + 1).

min(a,b) * (bi – ai)

min(3,4) * (4 – 3)

3 * 1 = 3

We compare the current maxArea, which is 28, to the new maxArea, which is 3.

28 > 3

maxArea remeins as 28

The eleventh loop

Finally, we hit the end of the loop.

Coding

And here’s the code to implement the previously explained methods.

Finally, here’s the actual code:

import java.io.*;
class containerWithMostWater {

    public static int maxArea(int[] a){
    int area = 0;
     
    for(int i = 0; i < a.length; i++)
        {
            for(int j = i + 1; j < a.length; j++)
            {
                area = Math.max(area, Math.min(a[i], a[j]) * (j - i));
            }
        }
        return area;
    }

    public static void main(String[] args) {
        int a[] = { 7,1,2,3,9 };
        System.out.println(maxArea(a));
    }
}