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:

source: leetcode.com

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/

Advertisements

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(n2 ).

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.

Advertisements

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/

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s