Container With Most Water LeetCode Solution


Frequently asked in Adobe Amazon Apple Arcesium Bloomberg ByteDance Flipkart Google Intel Intuit JP Morgan Microsoft Oracle Qualtrics Salesforce Samsung SAP Swiggy Tesla Uber VMware Yahoo
categories - Medium tiktok Walmart Wix ZomatoViews 99

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 ith 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:

Container With Most Water LeetCode Solution

 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 <= 105
  • 0 <= height[i] <= 104

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 –

Container With Most Water LeetCode SolutionContainer With Most Water LeetCode Solution 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://www.tutorialcup.com/leetcode-solutions/water-bottles-leetcode-solution.htm

 

 

 

Translate »