Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A container's width is the distance between its two lines, while its height is limited by the shorter line. Starting with the widest possible pair gives us a useful elimination rule: keeping the shorter line and moving the other endpoint inward cannot increase the area, because the width shrinks and the limiting height cannot improve. We can therefore discard the shorter endpoint without losing a better answer.

Approach

Place one pointer at each end of height and initialize the best area to zero.
Evaluate (right - left) * min(height[left], height[right]) and update the best area.
Move the pointer at the shorter line inward. When the heights are equal, either endpoint can be discarded; these implementations move the right pointer.
Continue until the pointers meet, then return the largest area seen. Each discarded endpoint has already been paired with its best remaining width, so no overlooked pair can improve the result.

class Solution:
    def maxArea(self, height: List[int]) -> int:
        l = 0
        r = len(height) - 1
        res = 0

        while l < r:
            res = max(res, (r - l) * min(height[l], height[r]))
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return res

Complexity analysis

Let n be height.length. The two pointers cross the array once, so the algorithm uses O(n) time and O(1) auxiliary space.