Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

Earn badges and level up

Introduction

This blog will discuss how to solve the container with the most water problem. Various approaches from brute force to the most optimized one will be discussed, and we will see their implementation in multiple languages.

Before diving into the solution to the container problem, let’s first briefly understand the problem statement.

Problem Statement

Given an array of size ‘N’ with non-negative elements. In this, each non-negative element represents a vertical line of the size of the elements placed on that ‘i^{th}’ index.

Our primary target is to get two lines, which will act as a container with the x-axis, and that container contains the most water. The container with the most problem should return the maximum area among all the containers that can store water.

Note: This container represents the area between two lines in which we can hold water, and we have to return the area of that container that can keep most of the water.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Examples

Input

Number of elements of the array (N) = 4

Array = [5, 8, 7, 9]

Output

Container with the most water = 16

Explanation

In this, array elements 1 and 3, i.e., 5 and 7 are two units apart. Therefore the size of the base is 2.

Height of the container = min(8, 9) = 8.

Therefore the total area = 8 * 2 = 16.

Approach 1: Brute Force Approach Using Nested Loops

This approach checks for all the possible pairs of boundaries, i.e., two array indexes acting as the walls of the container and calculating the area for each likely pair, and simply returning the overall maximum as the output.

Algorithm

Create a function ‘get_maximum_area()’ that will accept a single parameter, i.e., ‘arr’ - an array of all the given boundaries, or we can say the non-negative values of vertical lengths of that ‘ith’ index.

Make a nested iteration with ‘i’ and ‘j,’ in which the outer loop will be iterating from 0 to ’N’ the length of the array, and the inner loop of ‘j’ will traverse the array from ‘i + 1’ to the size of the array ‘N.’

Find the maximum area using the array of the container in which most of the water can be stored with the help of boundaries given in ‘arr[i]’ and ‘arr[j]’, which will be calculated as

Area = (j - i) * min(arr[i], arr[j])

If the calculated area is greater than the value in the ‘max_area’, then update the ’max_area’.

Return the ‘max_area.’

Dry Run

Let’s see a complete visualization of the brute force approach.

i = 0 , j = 1 , Area = base * height = 1 * 5 = 5, max_area = 5

i = 0 , j = 2 , Area = base * height = 2 * 5 = 10, max_area= 10

i = 0 , j = 3 , Area = base * height = 3 * 5 = 15, max_area = 15

i = 1 , j = 2 , Area = base * height = 1 * 7 = 7, max_area = 15

i = 1 , j = 3 , Area = base * height = 2 * 8 = 16, max_area = 16

i = 2 , j = 3 , Area = base * height = 1 * 7 = 7, max_area = 16

Conclusion:

The container with the most water i.e. with the maximum area is equal to 16 which is formed by indexes of the 1st and 3rd element of the array.

Implementation in C++ and Java

C++

Java

C++

#include
#include
using namespace std;
int maximum_area(vector &arr){
int N = arr.size();
// Variable used to store the result
int max_area = 0;
// Outer loop
for (int i = 0; i < N; i++){
// Inner Loop
for (int j = i + 1; j < N; j++){
// Updating max_area
max_area = max(max_area, min(arr[j], arr[i]) * (j - i));
}
}
return max_area;
}
int main(){
// Size of the input array
int N = 4;
// Non-negative elements of the array
vector arr(N);
arr[0] = 5;
arr[1] = 8;
arr[2] = 7;
arr[3] = 9;
// Function call to calculate maximum area
cout << "Container with most water = " << maximum_area(arr);
}

Java

public class MyClass {
static int N=0;
static int maximum_area(int arr[]){
// Variable used to store the result
int max_area = 0;
// Outer loop
for (int i = 0; i < N; i++){
// Inner Loop
for (int j = i + 1; j < N; j++) {
// Updating max_area
max_area = Math.max(max_area, Math.min(arr[j], arr[i]) * (j - i));
}
}
return max_area;
}
public static void main(String args[]) {
// Size of the input array
N=4;
// Declaration of array
int arr[];
arr = new int[N];
arr[0]= 5;
arr[1]= 8;
arr[2]= 7;
arr[3]= 9;
// Function call to calculate maximum area
System.out.print("Container with most water = ");
System.out.println(maximum_area(arr));
}
}

Output

Time Complexity

O(N^{2})

Explanation: In the call to ‘maximum_area()’, we are making a nested ‘for’ loop traversal, leading us to N^{2} iterations. In each iteration, we do one-line execution of time constant time complexity O(1). Therefore the overall time complexity will be O(N^{2}).

Space Complexity

O(1)

Explanation: As we use constant space, the overall space complexity will be O(1).

Note: Here, we are considering the space of the input array; if that’s regarded, the space complexity will be O(N).

Algorithm - 2 : Efficient Approach - Using Two Pointers

In this section, we will discuss the efficient approach for the problem “Container with Most Water” using two pointers where we have to create 2 pointers named low and high, and we will be computing the maximum amount of water that can be contained in the container.

Algorithm

Create the variables to store the area, low and high. Initialize the area, low and high, with 0, 0, n - 1, respectively.

Start an iteration from low to high.

Calculate the minimum height (min_height) between the elements at low and high using the min() function.

Calculate the difference (diff) between high and low.

Now, to calculate the area, there is a formula: max(diff * min_height, area).

The low or high can be moved; whichever element at the index will move. For example, if the element at the low index is smaller than the high index, then the low will be incremented by 1 else the high will be decremented by 1.

Implementation of Two Pointer Approach

C++

Java

Python

C++

#include
using namespace std;
int maxArea(vector < int > & height) {
// n is the size of given array "height".
int n = height.size();
/*
area is maximum amount of water, a container can store.
low and high are 0th and (n - 1)th index.
*/
int area = -1, low = 0, high = n - 1;
// iteration from low to high.
while (low < high) {
// taking minimum height between low and high values.
int min_height = min(height[low], height[high]);
// difference between high and low.
int diff = high - low;
// calculating maximum area.
area = max(diff * min_height, area);
/* move low and high according to the condition, whichever element is small will move. */
if (height[low] < height[high])
low++;
else
high--;
}
// returning the answer here.
return area;
}
int main() {
// given array "height".
vector < int > height = { 1, 8, 6, 2, 5, 4, 8, 3, 7 };
// computed answer printed.
cout << "Maximum Amount of water can be contained: " << maxArea(height);
return 0;
}

Java

import java.util.ArrayList;
import java.util.List;
public class ContainerWithMostWater {
public static int maxArea(List height) {
// n is the size of given array "height".
int n = height.size();
/*
area is maximum amount of water, a container can store.
low and high are 0th and (n - 1)th index.
*/
int area = -1, low = 0, high = n - 1;
// iteration from low to high.
while (low < high) {
// taking minimum height between low and high values.
int min_height = Math.min(height.get(low), height.get(high));
// difference between high and low.
int diff = high - low;
// calculating maximum area.
area = Math.max(diff * min_height, area);
/* move low and high according to the condition, whichever element is small will move. */
if (height.get(low) < height.get(high))
low++;
else
high--;
}
// returning the answer here.
return area;
}
public static void main(String[] args) {
List height = new ArrayList<>();
height.add(1);
height.add(8);
height.add(6);
height.add(2);
height.add(5);
height.add(4);
height.add(8);
height.add(3);
height.add(7);
System.out.println("Maximum Amount of water can be contained: " + maxArea(height));
}
}

Python

def max_area(height):
# n is the size of given array "height".
n = len(height)
"""
area is maximum amount of water, a container can store.
low and high are 0th and (n - 1)th index.
"""
area = -1
low, high = 0, n - 1
# iteration from low to high.
while low < high:
# taking minimum height between low and high values.
min_height = min(height[low], height[high])
# difference between high and low.
diff = high - low
# calculating maximum area.
area = max(diff * min_height, area)
# move low and high according to the condition, whichever element is small will move.
if height[low] < height[high]:
low += 1
else:
high -= 1
# returning the answer here.
return area
if __name__ == "__main__":
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print("Maximum Amount of water can be contained:", max_area(height))

Output

Time Complexity

O(N)

Explanation: Here, we are initializing low and high from 0 and n - 1, respectively, and in the worst case, one variable will be traversing the whole array, which is n. So the overall time complexity will be O(1).

Space Complexity

O(1)

Explanation: As we use constant space, the overall space complexity will be O(1).

Note: Here, we are considering the space of the input array; if that’s regarded, the space complexity will be O(N).

Frequently asked questions

Can the elements in the array in the above problem be negative?

No, it’s impossible to take negative elements in the array because each element represents the height of the line on that particular index, and height cannot be a negative value.

What is the best time complexity to find the container with the most water?

The most optimized solution comes up with the time complexity of O(N).

What is the best space complexity to find the container with the most water?

The most optimized solution comes up with the space complexity of O(1).

Conclusion

In this blog, we discussed the ‘Container with the most water’ problem, and the various approaches to solve this problem programmatically, and saw the implementation of 2 approaches in Java and C++. We also discussed the time and space complexity of both approaches and saw how smartly we can optimize an N^{2 }solution to a linear solution with constant space complexity.