Container With Most Water — LeetCode 11 Python Solution

The problem

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

Example

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.

Python solution

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

Complexity

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 11. Container With Most Water is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Related problems