Data Structures and Algorithms – Arrays – Container with Most Water

Problem:

Given an array of heights representing the ends of a container , find the container with the maximum area.

For example:

Consider the below input:

Input: height = [1,8,6,2,5,4,8,3,7]

The height can be represented pictorially as below:

Each line represents each height in the array in the order of the indices. You can join any two lines to form a container. Find the container with the maximum area.

Input:

[1,8,6,2,5,4,8,3,7]

Output:

49 as shown in the shaded area in the picture above.

Try out the solution here:

https://leetcode.com/problems/container-with-most-water/

Solution:

The brute force solution of this problem is to take each element and compare with each other element in the array. Take the minimum of these and multiply with the difference in their indices (which represents the breadth of the container). You should take the minimum of the heights else the water will overflow .

The maximum of the areas as calculated above gives the maximum area.

Here is the code:

class Solution {
    public int maxArea(int[] height) {
      
        
        int maxArea = 0;
        
        for(int i=0;i<height.length;i++){
            
            
            for(int j=i+1;j<height.length;j++){
                
                
                
                int length = Math.min(height[i],height[j]);
                
                int breadth = j-i;
                
                int area = length * breadth;
                
                if(area  > maxArea){
                    
                    maxArea = area;
                }
                
            }
        }
        
        return maxArea;
    }
}

The time complexity of the above code is O(n² ).

You can do better in O(n) time complexity.

Hint:

• Compare the first and last heights (assign a pointer to each of them) , take the minimum of them and multiply with their breadth (difference in their index positions)
• If the first height is less than the last height increase this pointer else decrease the other pointer and calculate the area again
• The max of the above areas gives the maximum area

This can be explained by the below gif (source: geekforgeeks):

ALGORITHM:

STEP1: Initialize maximum area to 0

STEP2: Initialize a variable to point to the left most element index(start index)

STEP3: Initialize a variable to point to the right most element index (end index)

STEP4: While left is less than right , find out the minimum of the heights in those indices and multiply it with the difference in the indices (represents breadth)

STEP4a: Compare this area with the maximum area and if it is greater , make it the maximum area

STEP4b: If the height pointed by the left pointer is less than that pointed by the right pointer , increment left pointer

STEP4c: If the height pointed by the right pointer is less than that pointed by the left , decrement right pointer

STEP5: Return maximum area.

Code:

Here is the code:

class Solution {
    public int maxArea(int[] height) {
      
        
        int maxArea = 0;
        
    
                
         int left = 0;
        
        int right = height.length-1;
        
        
        while(left < right){
            
            
            int breadth = right - left;
            int area = Math.min(height[left],height[right])*breadth;
            
            if(area > maxArea){
                
                maxArea = area;
            }
            
            if(height[left]< height[right]){
                
                left++;
            }else {
                
                right--;
            }
            
        }
        
        return maxArea;
    }
}

The time complexity is O(n) and space complexity is O(1).

That’s it!

References:

https://leetcode.com/problems/container-with-most-water/

https://www.geeksforgeeks.org/container-with-most-water/