LeetCode Challenge #11. Container With Most Water

Day 17 of 100 Days LeetCode Challenge

Question 12 of 75 - LeetCode Weekly Challenge

LeetCode Challenge #11. Container With Most Water

You are given an integer array height of length n. There are n vertical lines 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⁴

Java Video Solution

C++ Video Solution

Java Solution

				
					class Solution {
    public int maxArea(int[] height) {
        int start = 0 ;
        int end = height.length-1 ;
        int maxCap = 0 ;
        while(start<end){
            int h = Math.min(height[start],height[end]);
            int width = end - start ;
            int currCap = h * width ;
            maxCap = Math.max(currCap , maxCap );
            if(height[start]<height[end]){
                start++;
            }else{
                end--;
            }
        }
        return maxCap;
    }
}

C++ Solution

				
					class Solution {
public:
int maxArea(vector<int>& height) {
        int i=0;
        int j=height.size()-1;
        int ans=0;

        while(i<j)
        {
            if(height[i]<height[j])
            {
                ans=max(ans,((j-i)*height[i]));
                i++;
            }
            else
            {
                ans=max(ans,((j-i)*height[j]));
                j--;
            }
        }
        return ans;
    }
};

Code Explanation

In this function, we have to find two lines that together with the x-axis form a container, such that the container contains the most water. It is given that we cannot slant the container

Let’s see the step-by-step approach of the code:

There are two conditions in which the maximum amount of water can be stored –

either the container should have the maximum height

Or it should have the maximum width.

So, let’s take two pointers namely ‘i’ and ‘j’ where ‘i’ will be placed at the starting and ‘j’ will be placed at the end of the container. This is the condition of maximum water storage.

The ‘ans’ variable will store the maximum area encountered during the search.

3. Now, we will also check whether water is affected by height or not. Because height also plays a major role in determining the maximum water And rectify the height more or less accordingly to check the maximum water.

For this purpose, we have used a while loop that continues as long as ‘i’ is less than ‘j’.

Inside the loop, it checks whether the ‘height’ of ‘i’ is less than the ‘height’ at position ‘j’

if the ‘height[ i ]’ is less, then after calculating the area ( width* height), the area is stored in ‘ans’. If the calculated area is greater than the current ‘ans’ then ‘i’ is incremented.

if the other side wall is greater or the ‘height[ j ]’ is less or equal, it does the same calculations and ‘ans’ is updated, and the value of ‘j’ is decremented.

The loop continues until ‘i’ is no longer less than ‘j’.

Finally, the function returns the maximum area as ‘ans’.

Day 17 of 100 Days LeetCode Challenge

Question 12 of 75 - LeetCode Weekly Challenge