Leetcode: 11. Container With Most Water

• Pattern: Find optimal pair in array
• Pattern: Problem's constraints disallow \(O(n^2)\) solutions

Given an integer array \(height\) of length \(n\). A container is defined as a pair of indexes in \(height\), and it's volume as \(v(i, j)=\min(height[i], heght[j]) \times (i - j)\). The task is to find the container with maximum volume.

Let's use Two pointers technique to solve this problem. Let \(i=0\) and \(j=n-1\) be the two pointers starting on the beginning and end of the array. On each iteration, update the maximum volume found so far and move the pointers toward each other as following. If \(height[i]j\). It works since if \((i, j)\) isn't an optimal container, then the optimal container \((i', j')\) has height greater than \(min(height[i], height[j])\). In such case, the algorithm moves the side with smaller height since it certainly can't be part of an optimal container.

The time complexity is linear because each index of the array is used only once, and space complexity is constant as only variables to track the two points are necessary.

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

• Interview preparation: V