Container With Most Water

Problem

Given an array of heights, each describing a vertical line, choose two lines that together with the x-axis form a container holding the most water. Return that maximum area.

Approach

Start with the widest container: one pointer at each end. The area is the distance between them times the shorter of the two heights.

Then move the pointer at the shorter line inward. The shorter line caps the area, so keeping it and moving the taller line can only reduce the width without raising the cap. Moving the shorter line is the only move that might find a larger area.

Repeat until the pointers meet, keeping the best area seen.

Solution

class Solution:
    def maxArea(self, height: list[int]) -> int:
        left, right = 0, len(height) - 1
        best = 0

        while left < right:
            width = right - left
            best = max(best, width * min(height[left], height[right]))
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return best

Complexity

• Time: O(n): each step moves one pointer inward.
• Space: O(1).

Edge cases

• Two lines only: the answer is their distance times the shorter height.
• Equal heights at both ends: moving either pointer is safe.
• A zero-height line contributes no area.