Container With Most Water

The problem description can be found in LeetCode.

Approach

As usual, checking all possible pairs would require $O(n^2)$ time. However, we can still use the Two Pointers algorithm to reduce it to $O(n)$.

Let's derive some examples:

        |
    |   |
  | |   |
  | | | |
| | | | | |
1 3 4 2 5 1

The first value is bounded to its height. We cannot use a higher height to maximize the height itself, since only the minimum between the two will be used. So, for this first value, the maximum area we can obtain is with the last value.

At this point, we can avoid to consider the same height area again, since we cannot obtain a higher area with it. This means that we can discard this height from the search and go to the next one.

Solution

from typing import List


class Solution:
    def maxArea(self, heights: List[int]) -> int:
        ans = 0
        left, right = 0, len(heights) - 1

        while left < right:
            area = min(heights[left], heights[right]) * (right - left)
            ans = max(ans, area)
            if heights[left] < heights[right]:
                left += 1
            else:
                right -= 1

        return ans

Complexity

• Time: $O(n)$
• Space: $O(1)$

Where $n$ is the size of the heights¹ list.