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

Solution

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l,r = 0,len(height)-1
        maxw = 0
        while l<r:
            currw = min(height[l],height[r]) * (r-l)
            maxw = max(maxw,currw)
            if height[l] < height[r]:
                l+=1
            else:
                r-=1
        return maxw

Time Complexity: O(n)

Space Complexity: O(1)

Explanation

The actual code is trivial for this problem, however, the why this works is what's tricky.

The idea is, if we want to find the biggest container, we should greedily move the smallest line. The key idea is that for any two positions of l and r, the corresponding container area is larger than that of any container produced by moving the pointer with the larger height towards the other. All such containers therefore need not be considered.