Container with Most Water

Problem Statement

You are given an array $height[n]$ of integers of size n, where each value represents a coordinate position $(i, height[i])$. n vertical lines are drawn such that the endpoints of line i are at $(i, 0)$ and $(i, height[i])$. Find the container that is formed by two lines along with the x-axis, where the container contains the most water.

Example

Input – 1

height[] : [1, 5, 6, 3, 4, 2]

Output – 1

12

Explanation

The area shown in the blue section is the maximum area.

• 1 and 4 are distance 3 apart.
• Therefore, the size of the base = 3.
• Height of the container will be a minimum of $(5, 4)$ $= 4$
• Hence, The total area becomes $3 * 4$ $= 12$ units.

Input – 2

height[] :  [1, 1]

Output – 2

1

Explanation

Since there are only two endpoints, the area becomes $1 * 1$ $= 1$.

Constraints

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

Algorithm – 1 : Naive Approach – Using Nested Loops

Intuition

The most basic and straightforward approach for a container with the most water is to check all the possible pairs of boundaries and find out a team that has a maximum area.

Algorithm

1. Initialize a variable maxArea to track the current maximum area.
2. Run a nested loop, the outer loop from $i = 0$ to end $(n-1)$.
3. While the inner loop runs from $i+1$ to end $(n-1)$ with loop counter j.
4. Find the area for every pair of boundaries i and j, and store the area in the variable maxArea, where maxArea= $(j -i)$*$min(height[i], height[j])$. Update the variable maxArea, if the current area is greater than the maxArea.
5. Return the maxArea.

Code Implementation

Code in C++ :

#include <iostream>
using namespace std;

int maxContainer(int arr[], int n)
{
	int maxArea = 0;

        // Find the area for every pair of boundaries i and j
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
                    // Calculate the area
                    // and update the variable maxArea, if greater
                    maxArea = max(min(arr[j], arr[i]) * (j - i), maxArea);
		}
	}
	return maxArea;
}

// Driver code
int main()
{
	int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
	int height2[] = { 1, 1 };

    // Call the function for the first array
	int len1 = sizeof(height) / sizeof(height[0]);
	cout << maxContainer(height, len1);

    // Call the function for the second array
	int len2 = sizeof(height2) / sizeof(height2[0]);
	cout << endl << maxContainer(height2, len2);
}

Code in Java :

// Java code for Max
// Water Container
import java.io.*;

class Main{

    public static int maxContainer(int[] arr){
        int maxArea = 0;

        // Find the area for every pair of boundaries i and j
        for(int i = 0; i < arr.length; i++){
            for(int j = i + 1; j < arr.length; j++){
                // Calculate the area
                // and update the variable maxArea, if greater
                maxArea = Math.max(maxArea, Math.min(arr[i], arr[j]) * (j - i));
            }
        }
        return maxArea;
    }

    // Driver code
    public static void main(String[] args)
    {
        int height[] = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
        int height2[] = { 1, 1 };

        // Call the function for the first array
        System.out.println(maxContainer(height));

        // Call the function for the second array
        System.out.println(maxContainer(height2));
    }
}

Code in Python :

# Python code for Max
# Water Container
def maxContainer(arr, Len) :
	maxArea = 0

    # Find the area for every pair of boundaries i and j
	for i in range(Len) :
		for j in range(i + 1, Len) :

                    # Calculate the area
                    # and update the variable maxArea, if greater
                    maxArea = max(maxArea, min(arr[j], arr[i]) * (j - i))
	return maxArea

# Driver code
height = [ 1, 8, 6, 2, 5, 4, 8, 3, 7 ]
height2 = [ 1, 1 ]

len1 = len(height)
# Call the function for the first array
print(maxContainer(height, len1))

len2 = len(height2)
# Call the function for the second array
print(maxContainer(height2, len2))

Output :

49
1

Time Complexity :

The time complexity is $O(n^2)$. Since two nested loops traverse the array.

Space Complexity :
The space complexity is $O(1)$. Since no extra space is used in the solution of the container with the most water.

Algorithm – 2 : Efficient Approach – Using Two Pointers

Intuition

We take two pointers, one at the start and one at the end of the array, and we keep track of the maximum area between the lines in a variable maxArea. At each step, we calculate the area formed by the two pointers, update the maximum area, and move the pointer pointing to the shorter line by one to the opposite end.

Check the below illustration of two pointer approach to solving container with most water problem :

Algorithm

1. Initialize a variable maxArea to track the current maximum area of a container with the most water.
2. Keep two indices, $i$ and $j$ initialized at 0 and $n-1$, respectively.
3. Run a loop until the left index i is less than the right index j.
4. Calculate the area formed between indices i and j, where area $= Math.min(height[i], height[j]) * (j – i))$ and update the maxArea.
5. If the value at $height[i]$ is lesser than $height[j]$ then move index i by one right. Else move index j by one left.
6. Return the maxArea.

Code Implementation

Code in C++ :

// C++ code for Max
// Water Container
#include<iostream>
using namespace std;

int maxContainer(int arr[], int n){
    int i = 0;
    int j = n -1;
    int maxArea = 0;

    while (i < j){
        // Calculate the area
        // and update the variable maxArea, if greater
        maxArea = max(maxArea, min(arr[i], arr[j]) * (j - i));

        if (arr[i] < arr[j])
            i += 1;
        else
            j -= 1;
    }
    return maxArea;
}

// Driver code
int main()
{
	int height[] = {1, 8, 6, 2, 5, 4, 8, 3, 7};
	int height2[] = { 1, 1 };

	int len1 = sizeof(height) / sizeof(height[0]);
    // Call the function for first array
	cout << maxContainer(height, len1);

	int len2 = sizeof(height2) / sizeof(height2[0]);
    // Call the function for second array
	cout << endl << maxContainer(height2, len2);
}

Code in Java :

// Java code for Max
// Water Container
import java.util.*;

class Area{

    public static int maxContainer(int arr[]){
        int i = 0;
        int j = arr.length - 1;
        int maxArea = 0;

        while (i < j){
            // Calculate the area
            // and update the variable maxArea, if greater
            maxArea = Math.max(maxArea,
                        Math.min(arr[i], arr[j]) * (j - i));

            if (arr[i] < arr[j])
                i += 1;
            else
                j -= 1;
        }
        return maxArea;
    }

    public static void main(String[] args)
    {
        int height[] = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
        int height2[] = { 1, 1 };

        // Call the function for the first array
        System.out.println(maxContainer(height));

        // Call the function for the second array
        System.out.println(maxContainer(height2));
    }
}

Code in Python :

# Python3 code for Max
# Water Container
def maxContainer(arr):
	i = 0
	j = len(arr) -1
	maxArea = 0

	while i < j:
            # Calculate the area
            # and update the variable maxArea, if greater
            maxArea = max(maxArea, min(arr[i], arr[j]) * (j - i))

        if arr[i] < arr[j]:
            i += 1
        else:
            j -= 1
	return maxArea

# Driver code
height = [ 1, 8, 6, 2, 5, 4, 8, 3, 7 ]
height2 = [ 1, 1 ]

# Call the function for the first array
print(maxContainer(height))

# Call the function for the second array
print(maxContainer(height2))

Output :

49
1

Time Complexity :
The time complexity is $O(n)$. Since only one traversal of the array is required.

Space Complexity :
The space complexity is $O(1)$. Since no extra space is used in the solution of the container with the most water.

Conclusion

• We have given an integer array $height[n]$ of length n, where each value refers to a coordinate position $(i, height[i])$.
• We have to find the two lines that form a container along with the x-axis, such that the container contains the most water.
• For eg, If the array is $[1,8,6,2,5,4,8,3,7]$, the size of the base $= 7$, Height of the container will be 7 and the area becomes $7*7 = 49$ units.
• The naive approach takes $O(n^2)$ time complexity as two loops were used, and $O(1)$ space complexity because no extra space is used.
• On the other hand, the efficient approach for a container with most water is using the Two-pointer Technique. It takes $O(n)$ time complexity and $O(1)$ as space complexity.
• We initialize a variable maxArea in both approaches to track the current maximum area.

FAQs

Q. How can the area between two points be calculated ?

A. The length is the distance between the two endpoints, and the minimum of the two heights is going to be the height because each consecutive block’s width is considered to be 1. Hence, area $= Math.min(height[i], height[j]) * (j – i))$.

Q. What is the most efficient approach to solve this problem ?

A. The most efficient approach for a container with the most water is using the Two-pointer Technique because it takes $O(n)$ time complexity and $O(1)$ as space complexity.

Q. Similar Coding questions to practice?

A. Refer to Trapping Rain Water

• Refer Triplet with Zero Sum