Container With Most Water

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

1. 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.
    
2. 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.’
    
3. 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])
      
4. If the calculated area is greater than the value in the ‘max_area’, then update the ’max_area’.
    
5. 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);
}

You can also try this code with Online C++ Compiler

Run Code

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));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

Time Complexity

O(N²)

Explanation: In the call to ‘maximum_area()’, we are making a nested ‘for’ loop traversal, leading us to N² 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²).

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

1. Create the variables to store the area, low and high. Initialize the area, low and high, with 0, 0, n - 1, respectively.
    
2. Start an iteration from low to high.
    
3. Calculate the minimum height (min_height) between the elements at low and high using the min() function.
    
4. Calculate the difference (diff) between high and low.
    
5. Now, to calculate the area, there is a formula: max(diff * min_height, area).
    
6. 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;
}

You can also try this code with Online C++ Compiler

Run Code

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));
   }
}

You can also try this code with Online Java Compiler

Run Code

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))

You can also try this code with Online Python Compiler

Run Code

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² solution to a linear solution with constant space complexity.
 

Recommended Reading:

• Distance from Next Greater Element
• Next Greater and Smaller Element for Every Element in an Array
• The Largest Rectangular Area in a Histogram
   

Do check out The Interview guide for Product Based Companies, as well as some of the popular interview problems, asked in top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests, Test Series, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Coding!