DEV Community

Cover image for Solving the "Container With Most Water" Problem on Leet Code
Leetcode
Leetcode

Posted on

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Happy coding,
shiva

Top comments (0)