Solving the "Container With Most Water" Problem on Leet Code

11. Container With Most Water

Type : Medium
Liked by: 26.5K
Disliked by: 1.4K

Companies that asked this Question
Companies : No of Times asked

Microsoft 4
Google 4
Amazon 3
Adobe 2
Bloomberg 2
Apple 9
Facebook 4
Uber 3
Oracle 2
TikTok 2
Goldman Sachs 5
Intel 4
Swiggy 4
ByteDance 3
VMware 3
Qualtrics 3
Intuit 3
Flipkart 2
Zoho 2
Samsung 2
eBay 2
Walmart Labs 2
Yandex 2
Yahoo 2
Cisco 2
tcs 2
Tesla 2
C3 IoT 2
Arcesium 2
DE Shaw 2
JPMorgan 2
Wix 1

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

Intuition:

The code aims to find the maximum area between two lines in a histogram, where the lines represent the heights of bars.

Approach:

• Initialize pointers at both ends of the histogram (LeftPointer at 0 and RightPointer at the last element).
• While the LeftPointer is less than the RightPointer:
• Calculate the area between the lines formed by the heights at LeftPointer and RightPointer.
• Update the MaximumArea if the current area is greater.
• Move the pointer that points to the shorter line inward (towards the other pointer).
• Repeat step 2 until the pointers meet.

Complexity:

Time complexity: O(n) where n is the number of elements in the height array. We iterate through the array once.
Space complexity: O(1) because we use a constant amount of extra space regardless of the input size.

Code:

class Solution {
    public int maxArea(int[] height) {
        int MaximumArea = 0;
        int LeftPointer = 0;
        int RightPointer = height.length - 1;

        while(LeftPointer < RightPointer){
            if(height[LeftPointer] < height[RightPointer]){
                MaximumArea = Math.max(MaximumArea , height[LeftPointer] *(RightPointer - LeftPointer));
                LeftPointer++;
            }
            else{
                MaximumArea = Math.max(MaximumArea ,height[RightPointer] *(RightPointer - LeftPointer));
                RightPointer--;
            }
        }

        return MaximumArea;
    }
}

Happy coding,
shiva