LeetCode 11: Container With Most Water

Problem Restatement

We are given an integer array height.

There are n vertical lines.

The ith line has endpoints:

(i, 0)
(i, height[i])

Choose two lines. Together with the x-axis, they form a container.

The amount of water the container can hold depends on:

1. the distance between the two lines
2. the shorter of the two heights

The goal is to return the maximum amount of water any pair of lines can hold.

The container cannot be slanted. The LeetCode statement defines the area using two vertical lines and the x-axis.

Input and Output

Example function shape:

def maxArea(height: list[int]) -> int:
    ...

Examples

Example 1:

height = [1,8,6,2,5,4,8,3,7]

The best pair is:

index 1, height 8
index 8, height 7

Width:

8 - 1 = 7

Container height:

min(8, 7) = 7

Area:

7 * 7 = 49

Output:

49

Example 2:

height = [1,1]

There are only two lines.

Width:

1

Height:

1

Area:

1

Output:

1

First Thought: Try Every Pair

The most direct solution is to check every pair of lines.

For each pair (i, j):

i < j

Compute:

area = (j - i) * min(height[i], height[j])

Keep the largest area.

Code:

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

        for i in range(n):
            for j in range(i + 1, n):
                width = j - i
                h = min(height[i], height[j])
                best = max(best, width * h)

        return best

This is easy to understand and correct, but it checks too many pairs.

Problem With Brute Force

There are O(n^2) pairs of lines.

For large input, this is too slow.

We need a linear-time method.

Key Insight

The area is:

width * min(left_height, right_height)

Start with the widest possible container:

left = 0
right = n - 1

This gives the maximum possible width.

Now we decide which pointer to move.

If:

height[left] < height[right]

then the left line is the limiting height.

Moving the right pointer inward makes the width smaller, while the limiting left height stays the same or lower. So keeping the same left line cannot produce a better area by moving only the right pointer.

Therefore, we should move the shorter side.

The only chance to improve the area after width shrinks is to find a taller limiting line.

Why Move the Shorter Line

Suppose:

height[left] <= height[right]

The current area is:

(right - left) * height[left]

Now consider any container using the same left and a smaller right index k, where:

left < k < right

Its width is smaller:

k - left < right - left

Its height is at most:

height[left]

because the shorter side cannot exceed height[left].

So its area cannot exceed the current area.

That means after checking (left, right), no better answer can be found using the current left.

So we safely move left forward.

The same reasoning applies symmetrically when height[right] < height[left].

Visual Walkthrough

Use:

height = [1,8,6,2,5,4,8,3,7]

Start:

left = 0
right = 8

Area:

width = 8
height = min(1, 7) = 1
area = 8

The left side is shorter, so move left.

Now:

left = 1
right = 8

Area:

width = 7
height = min(8, 7) = 7
area = 49

This becomes the best answer.

Now the right side is shorter, so move right.

The scan continues until the two pointers meet.

The largest area found is:

49

Algorithm

1. Set left = 0.
2. Set right = len(height) - 1.
3. Set best = 0.
4. While left < right:
   • compute the current width
   • compute the current height using the shorter line
   • update best
   • move the pointer at the shorter line
5. Return best.

Correctness

At every step, the algorithm checks the container formed by left and right.

If height[left] <= height[right], then height[left] limits the current container.

Any container that keeps the same left but moves right inward has smaller width and height no greater than height[left]. Therefore, it cannot have a larger area than the current container.

So after checking the current pair, the algorithm can discard left.

If height[right] < height[left], the symmetric argument shows that the algorithm can discard right.

Each step discards only a line that cannot participate in a better unseen container.

Since the algorithm keeps the best area among all checked containers and safely removes impossible boundary lines, it returns the maximum possible area.

Complexity

Implementation

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

        while left < right:
            width = right - left
            h = min(height[left], height[right])

            best = max(best, width * h)

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

        return best

Code Explanation

Initialize the two pointers at both ends:

left = 0
right = len(height) - 1

This starts with the widest possible container.

Compute the current width:

width = right - left

Compute the limiting height:

h = min(height[left], height[right])

Update the best area:

best = max(best, width * h)

Then move the shorter side:

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

Finally:

return best

Testing

def run_tests():
    s = Solution()

    assert s.maxArea([1,8,6,2,5,4,8,3,7]) == 49
    assert s.maxArea([1,1]) == 1
    assert s.maxArea([4,3,2,1,4]) == 16
    assert s.maxArea([1,2,1]) == 2
    assert s.maxArea([2,3,4,5,18,17,6]) == 17
    assert s.maxArea([1,2,4,3]) == 4

    print("all tests passed")

run_tests()