Container With Most Water¶

Problem¶

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

Approach¶

Start with two pointers at the outermost lines. The area is limited by the shorter line, so always move the pointer at the shorter side inward to try for a taller line.

When to Use¶

Maximizing area/product with two boundaries — shrink from both ends, always moving the weaker constraint inward. Keywords: "maximize rectangle", "widest pair", "two-boundary optimization".

Complexity¶


Time	`O(n)`
Space	`O(1)`

Implementation¶

SolutionTestsChallenge

container_with_most_water ¶

Container With Most Water — max area between two vertical lines.

Problem

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

Approach

Start with two pointers at the outermost lines. The area is limited by the shorter line, so always move the pointer at the shorter side inward to try for a taller line.

When to use

Maximizing area/product with two boundaries — shrink from both ends, always moving the weaker constraint inward. Keywords: "maximize rectangle", "widest pair", "two-boundary optimization".

Complexity

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

max_area ¶

max_area(height: Sequence[int]) -> int

Return the maximum water area between any two lines in height.

max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) 49

Source code in src/algo/two_pointers/container_with_most_water.py

def max_area(height: Sequence[int]) -> int:
    """Return the maximum water area between any two lines in *height*.

    >>> max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])
    49
    """
    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

tests/two_pointers/test_container_with_most_water.py

"""Tests for the container-with-most-water problem."""

from hypothesis import given
from hypothesis import strategies as st

from algo.two_pointers.container_with_most_water import max_area


class TestMaxArea:
    def test_basic(self) -> None:
        assert max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49

    def test_two_lines(self) -> None:
        assert max_area([1, 1]) == 1

    def test_ascending(self) -> None:
        assert max_area([1, 2, 3, 4, 5]) == 6  # min(2,5)*3=6

    def test_descending(self) -> None:
        assert max_area([5, 4, 3, 2, 1]) == 6  # min(5,2)*3=6

    def test_equal_heights(self) -> None:
        assert max_area([4, 4, 4, 4]) == 12  # min(4,4)*3=12

    def test_empty_and_single(self) -> None:
        assert max_area([]) == 0
        assert max_area([5]) == 0

    @given(
        data=st.lists(
            st.integers(min_value=0, max_value=100),
            min_size=2,
            max_size=50,
        ),
    )
    def test_result_matches_brute_force(self, data: list[int]) -> None:
        expected = 0
        for i in range(len(data)):
            for j in range(i + 1, len(data)):
                expected = max(expected, min(data[i], data[j]) * (j - i))
        assert max_area(data) == expected

Implement it yourself

Run: just challenge two_pointers container_with_most_water

Then implement the functions to make all tests pass. Use just study two_pointers for watch mode.

Reveal Solution

container_with_most_water ¶

Container With Most Water — max area between two vertical lines.

Problem

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

Approach

Start with two pointers at the outermost lines. The area is limited by the shorter line, so always move the pointer at the shorter side inward to try for a taller line.

When to use

Maximizing area/product with two boundaries — shrink from both ends, always moving the weaker constraint inward. Keywords: "maximize rectangle", "widest pair", "two-boundary optimization".

Complexity

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

max_area ¶

max_area(height: Sequence[int]) -> int

Return the maximum water area between any two lines in height.

max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]) 49

Source code in src/algo/two_pointers/container_with_most_water.py

def max_area(height: Sequence[int]) -> int:
    """Return the maximum water area between any two lines in *height*.

    >>> max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])
    49
    """
    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