Container with most water | February LeetCoding Challenge 2021 | Day 17
logo
Manas Sinha
Developer | Designer

By Manas | 17 February 2021

February LeetCoding Challenge 2021

Day 17

CONTAINER WITH MOST WATER

PROBLEM  STATEMENT:
Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai)n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water. Note 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
Example 3
Input: height = [4,3,2,1,4]
Output: 16
Example 4
Input: height = [1,2,1]
Output: 2
Constraints:
  • n == height.length
  • 2 <= n <= 3 * 104
  • 0 <= height[i] <= 3 * 104
The aim is to maximize the area formed between the vertical lines. The area of any container is calculated using the shorter line as length and the distance between the lines as the width of the rectangle.
Area = length of shorter vertical line * distance between lines

Start with the maximum width container and go to a shorter width container if there is a vertical line longer than the current containers shorter line. This way we are compromising on the width but we are looking forward to a longer length container

Explanation

A naive approach to solve this problem would be to check all the possible combinations. The time complexity of which will be O(n2). Efficient approach: Start with left pointer at start element and right pointer at last element and find how much water it containes. Now if the height of left index is less than the right index increase the left index else decrease the right index
ALGORITHM:
  • Declare three variables left, right, and max_water and, initialise it with 0, N-1 and 0 respectively.
  • Calculate how much water is between left and right pointers and check if it is more than current max.
  • If the height at left index is less than right, move left one step forward else move right one step backwards.
  • Repeat until left exceeds right.
Time complexity : O(n)
Image credit : Geeks for Geeks
gif

code

C++

//C++
class Solution {
public:
    int maxArea(vector<int>& height) {
        int max_water = 0;
        int left = 0;
        int right =  height.size()-1;
        
        while(left<right){
            int temp = min(height[left],height[right])*(right-left);
            max_water = max(max_water,temp);
            if(height[left] < height[right]){
                ++left;
            }
            else{
                --right;
            }
        }
        return max_water;
    }
};

Python

#Python3
class Solution:
    def maxArea(self, height: List[int]) -> int:
        left=0
        right=len(height)-1
        max_water=0
        while left<right:
            temp = min(height[left],height[right])*(right-left)
            max_water = max(max_water,temp)
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1
        return max_water
        

LEAVE A COMMENT

If you like the post leave a comment and share it.

Leave a Reply