11. Container With Most Water

Problem¶

Given vertical line heights, choose two lines maximizing the contained area:

height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
best lines = indices 1 and 8
area = (8 - 1) * min(8, 7) = 49
output = 49

Key trick¶

Start with the widest container and move only the shorter line inward. Moving the taller line cannot improve the limiting height, while the width always decreases.

Trap¶

• Moving the taller pointer can discard the optimum.
• Tracking the best left and right endpoints independently is invalid because the area depends on the pair.
• Forgetting the width is the index difference, not the number of elements between the lines.

Why is it interesting?¶

A local elimination argument reduces an apparent \(O(n^2)\) search over all pairs to a single \(O(n)\) two-pointer scan.

Python solution¶

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

        while l < r:
            # Evaluate the current widest remaining container.
            best = max(best, (r - l) * min(height[l], height[r]))

            # Only replacing the shorter line can produce a larger area.
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1

        return best

Time complexity: \(O(n)\).

Space complexity: \(O(1)\).

Comment on my solution¶

Your two-pointer direction is promising, but l_max and r_max are updated independently. An endpoint that is unhelpful with the currently saved opposite endpoint may form the optimal pair with a later endpoint, so your updates can permanently discard the answer.

For the failing case, the optimum uses heights 18 and 17 at adjacent indices, but the retained endpoints are chosen according to their areas with other endpoints. Evaluate every current pair directly and move the shorter pointer; no endpoint tuples are needed.

# Wrong Answer: 51/65 testcases passed
# [2,3,4,5,18,17,6]
# Output: 16
# Expected: 17
class Solution:
    def maxArea(self, height: list[int]) -> int:
        l, r = 0, len(height) - 1
        l_max = (0, height[l]) # index, height
        r_max = (len(height) - 1, height[r]) # index, height

        def area(left, right):
            return min(left[1], right[1]) * (right[0] - left[0])

        while l < r:
            if height[l] < height[r]:
                l += 1
                if area((l, height[l]), r_max) > area(l_max, r_max):
                    l_max = (l, height[l])
            else:
                r -= 1
                if area(l_max, (r, height[r])) > area(l_max, r_max):
                    r_max = (r, height[r])
        return area(l_max, r_max)