11. Container With Most Water (Python)

Related Topic

Two-Pointers.

Description

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Sample I/O

Example 1

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.

Note

You may not slant the container and n is at least 2.

Methodology

We use two pointers to solve this question. First we set left pointer which is the start of the list and right pointer which is the end of the list. we compare the area of the container that made by left and right to the max area. If the current area is larger than the max area, we update the max area to the current area. We will move the pointer with shorter height closer to the other pointer until two pointer get touched.

Code

def maxArea(self, height: List[int]) -> int:
        left,right =0, len(height)-1
        result = 0
        
        while left < right:
            water = (right-left) * min(height[left], height[right])
            if water > result:
                result = water
            if height[left] < height[right]:
                left+=1
            else:
                right-=1
        return result

BigO

Iterate the element of the list once, so total time complexity is O(n)