roadmap/two-pointers/Container With Most Water

Container With Most Water

MediumAmazonGoogleFacebookBloombergApple

Problem

Given n non-negative integers representing heights at positions 0..n-1, find two lines that form a container holding the most water.

Intuition — the key insight

Area = min(height[lo], height[hi]) × (hi - lo). With two pointers at the ends, moving the taller pointer inward can never increase area (width shrinks, height bounded by the same minimum). Moving the shorter pointer might increase area. So always move the shorter pointer.

Approach

Two pointers from edges

lo = 0, hi = n-1. Compute area. Move the pointer pointing to the shorter height inward. Repeat until pointers meet.

Complexity

Time

O(n)

Space

O(1)

Single pass with two pointers.

Solution code

Python

def maxArea(self, height: List[int]) -> int:
    lo, hi = 0, len(height) - 1
    best = 0
    
    while lo < hi:
        area = min(height[lo], height[hi]) * (hi - lo)
        best = max(best, area)
        
        if height[lo] < height[hi]:
            lo += 1
        else:
            hi -= 1
    
    return best

Edge cases to remember

⚠Two elements: only one container possible

⚠All same heights: area = height × (n-1)

Hints

What pattern do you think this problem uses?