Container With Most Water LeetCode Solution

Problem Statement

Container With Most Water LeetCode Solution says that – You are given an integer array height of length n. There are n vertical lines are drawn such that the two endpoints of the i^th line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

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

Output:

 49

Explanation:

 The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input:

 height = [1,1]

Output:

 1

Constraints:

• n == height.length
• 2 <= n <= 10⁵
• 0 <= height[i] <= 10⁴

ALGORITHM –

IDEA –

• In order to find Container With Most Water. We will Focus on the maximum area covered between two vertical lines representing the maximum amount of water contained by the container.
• So our final answer will be (height between two vertical * distance between them). so what we will do first we will take two pointers one pointer start from 0 and another from last and we will compare the height and  the height which will be smaller we will take that height and multiply distance between both the heights.
• After that if height[i] > height[j] then decrease the pointer from last and if height[i] < height[j] then increase the pointer i by 1 and update res with maximum and at last we will return a maximum one.

APPROACH –

• First we will make two pointer i = 0,j = length of array and one variable res = 0.
• After that, we will traverse the array and check for the condition if height[i] > height[j] then calculate the area and update res.
• Then Decrement in j by 1 else same condition will happen instead of decrement we will increase the i by 1 and return res.
• Hence, Container With Most Water will be calculated.

Image of Container With Most Water LeetCode Solution –

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

class Solution:
    def maxArea(self, height: List[int]) -> int:
        
        i = 0
        j = len(height)-1
        res = 0
        
        while(i < j):
            
            if height[i] > height[j]:
                res = max(res,min(height[i],height[j])*(j-i))
                
                j-=1
                
            else:
                res = max(res,min(height[i],height[j])*(j-i))
                i += 1
                
        return res

Time Complexity: O(N), As we have traversed the whole array only once.

Space Complexity: O(1), As we have not taken any Extra Space.

SIMILAR QUESTION – https://tutorialcup.com/leetcode-solutions/water-bottles-leetcode-solution.htm