Container With Most Water

You are given an integer array heights where heights[i] represents the height of the $i^{th}$ bar.

You may choose any two bars to form a container. Return the maximum amount of water a container can store.

Approach

Use two pointers at the left and right ends. The area is limited by the shorter height, so compute the area and move the pointer at the shorter bar inward to potentially find a taller bar. Track the maximum area seen across all positions.

Why It Works

With pointers at l and r, any container using the shorter height cannot get larger by moving the taller pointer inward, since the height limit stays the same or decreases while width shrinks. Moving the shorter pointer is the only way to potentially increase the limiting height, so this strategy explores all candidates that can beat the current best.

Complexity

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

Reference Implementation (Python)

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        best = 0
        while left < right:
            h = min(height[left], height[right])
            best = max(best, h * (right - left))
            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1
        return best