🌊11. Container With Most Water

Medium | Grind 75 | January 6th Friday, 2022

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 is (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.

Constraints:

• n == height.length

• 2 <= n <= 10^5

• 0 <= height[i] <= 10^4

Example 1

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

SOLUTION

To find the maximum volume of water that can be contained between two bars, we must maximize the width and height of the container. To maximize the width, we iterate through the list from the two endpoints. We then choose the smaller of the two heights at the endpoints as the height of the container. This ensures that the maximum area for that height is achieved. If the left height is smaller, we increment the left endpoint and decrement the right endpoint if it is smaller. This process is repeated until the left pointer meets the right pointer, at which point we will have found the maximum volume of water that can be contained between the bars.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        """
            We need to maximize the area so we start with the leftmost and the 
            rightmost points.
            1. two pointers: left and right 
            2. Calculate the area: 
                height = min(height[left], height[right]) 
                width = right - left
            3. Increment start if height[left] < height[right] else decrement end 
                -increment/decrement the smaller pointer because the maximum potential 
                area for that pointer value has been reached since we traverse
                from the ends. 
            2. repeat step one until all the two pointers converge.   
        """
        # two pointers at each end of the height list
        left, right = 0, len(height)-1

        # maximum area we can obtain 
        max_area = 0

        while left < right: 
            width = right - left

            """ can only use the min-height """
            if height[left] < height[right]: 
                max_area = max(max_area, height[left]*width)
                left += 1
            
            else: 
                max_area = max(max_area, height[right]*width)
                right -= 1
        
        return max_area

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the length of the height list. We iterate over all the elements in the list once.

SPACE: O(1). Space is constant since we only need a single variable to store the maximum area and two other variables to store the index.

* Written with help from ChatGPT *