Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Examples
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Approach 1: Brute Force Approach Using Nested Loops
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation in C++ and Java
4.4.
C++
4.5.
Java
4.5.1.
Output
4.6.
Time Complexity
4.7.
Space Complexity 
5.
Algorithm - 2 : Efficient Approach - Using Two Pointers
5.1.
Algorithm
5.2.
Implementation of Two Pointer Approach
5.3.
C++
5.4.
Java
5.5.
Python
5.6.
Time Complexity
5.7.
Space Complexity
6.
Frequently asked questions
6.1.
Can the elements in the array in the above problem be negative?
6.2.
What is the best time complexity to find the container with the most water?
6.3.
What is the best space complexity to find the container with the most water?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Container With Most Water

Author Sahil Setia
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
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.

container with most water

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 ‘ith’ 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.

Example of Container With Most Water

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
Brute Force Approach Base 1
  • i = 0 , j = 2 , Area = base * height = 2 * 5 = 10, max_area = 10
Brute Force Approach Base 2
  • i = 0 , j = 3 , Area = base * height = 3 * 5 = 15, max_area = 15
Brute Force Approach Base 3
  • i = 1 , j = 2 , Area = base * height = 1 * 7 = 7, max_area = 15
Brute Force Approach Base 4
  • i = 1 , j = 3 , Area = base * height = 2 * 8 = 16, max_area = 16
Brute Force Approach Base 5
  • i = 2 , j = 3 , Area = base * height = 1 * 7 = 7, max_area = 16
Brute Force Approach Base 6

 

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

Brute Force Approach 2

Time Complexity

O(N2)

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

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

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

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

Recommended Reading:

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!

Previous article
Implement a Dictionary using Trie
Next article
Longest Common Prefix Using Trie
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass