Container With Most Water

Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:

Input: height = [1,1]
Output: 1

Constraints:

n == height.length
2 <= n <= 10^5
0 <= height[i] <= 10^4

Solution

Approach: Two Pointers (Greedy)

The key insight is to start with the widest possible container (pointers at both ends) and move inward. The area is determined by the shorter of the two lines and the distance between them: area = min(height[left], height[right]) * (right - left).

We greedily move the pointer pointing to the shorter line inward, because moving the taller line would only decrease the width without any chance of increasing the height.

Implementation

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

        while left < right:
            # Calculate current area
            width = right - left
            current_height = min(height[left], height[right])
            current_area = width * current_height

            max_area = max(max_area, current_area)

            # Move pointer pointing to shorter line
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

Alternative (More Concise):

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

        while left < right:
            max_area = max(max_area, min(height[left], height[right]) * (right - left))

            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area

Complexity Analysis

Time Complexity: O(n), where n is the length of the array. We traverse the array once with two pointers moving toward each other.
Space Complexity: O(1). We only use a constant amount of extra space.

Key Insights

Greedy Approach Works: We might think we need to check all pairs (O(n²)), but the greedy two-pointer approach is optimal. We always move the shorter pointer because moving the taller one cannot increase the area.
Area Formula: Area = min(height[left], height[right]) * (right - left). The height is limited by the shorter line (water would overflow otherwise).
Why Move the Shorter Pointer? If we move the taller pointer, the width decreases and the height can only stay the same or decrease (limited by the other line). If we move the shorter pointer, the width still decreases but we have a chance of finding a taller line that increases the area.
Start Wide: Starting from the widest container ensures we don’t miss the optimal solution. As we move inward, we trade width for potentially more height.
No Need to Track Positions: We only need to track the maximum area, not which two lines form it. This simplifies the solution.