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

## 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

## 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
``````