DSA Container with Most Water

The problem

Container With Most Water places vertical walls in a row. Two walls and the space between them form a container. The task is the largest amount of water any pair of walls can hold.

The water amount is an area. The area is the gap between the walls times the height of the shorter wall. The shorter wall sets the water level, because water spills over it first.

cases = [
    ([1, 8, 6, 2, 5, 4, 8, 3, 7], 49),
    ([1, 1], 1),
    ([4, 3, 2, 1, 4], 16),
    ([1, 2, 1], 2),
]
for heights, expected in cases:
    print(heights, 'best area:', expected)

Intuition

The widest pair is the first idea. Take the two outermost walls. The gap is as large as it can be.

Width alone does not win. A short outer wall caps the level, and a narrower pair of tall walls can hold far more. Fixing one wall and scanning partners has the same flaw in reverse: the fixed wall may be the cap that no partner can lift.

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
wide = (8 - 0) * min(heights[0], heights[8])
tall = (8 - 1) * min(heights[1], heights[8])
print('widest pair, walls 1 and 7: area', wide)
print('narrower pair, walls 8 and 7: area', tall)

Brute force

The brute force tries every pair of walls. Each pair gives one area. The largest area wins.

def max_area_brute(heights):
    best = 0
    pairs = 0
    for left in range(len(heights)):
        for right in range(left + 1, len(heights)):
            pairs += 1
            area = (right - left) * min(heights[left], heights[right])
            if area > best:
                best = area
    return best, pairs

for heights in [[1, 8, 6, 2, 5, 4, 8, 3, 7], [4, 3, 2, 1, 4], [1, 2, 1]]:
    best, pairs = max_area_brute(heights)
    print(heights, 'best:', best, 'pairs tried:', pairs)

The answer is correct. The pair count grows with the square of the wall count. Most of those pairs can be ruled out without scoring them.

The optimal solution: move the shorter wall

The key idea is to move the shorter wall inward. Moving the taller wall keeps the same level and only shrinks the gap, so that move can never improve the area.

def max_area(heights):
    left = 0
    right = len(heights) - 1
    best = 0
    while left < right:
        area = (right - left) * min(heights[left], heights[right])
        if area > best:
            best = area
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return best

cases = [[1, 8, 6, 2, 5, 4, 8, 3, 7], [1, 1], [4, 3, 2, 1, 4], [1, 2, 1]]
for heights in cases:
    print(heights, 'best area:', max_area(heights))

Walkthrough

Take the walls [1, 8, 6, 2, 5, 4, 8, 3, 7]. The pointers start on the outermost walls. Each step scores one container and then moves the shorter wall.

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
left = 0
right = len(heights) - 1
best = 0
while left < right:
    area = (right - left) * min(heights[left], heights[right])
    if area > best:
        best = area
    print('walls', heights[left], 'and', heights[right], 'area', area, 'best', best)
    if heights[left] < heights[right]:
        left += 1
    else:
        right -= 1
print('final best:', best)

The first container scores only 8. Its left wall of height 1 is the cap, so that wall moves. The best container pairs the walls of height 8 and 7, for 7 times 7, which is 49.

Complexity

Time is O(n). Each step moves one pointer inward, and each wall leaves the scan once.

Space is O(1). Two indices, one area and one best value are the only extra storage.

def brute_pairs(n):
    return n * (n - 1) // 2

for n in [9, 20, 40]:
    print('walls', n, 'brute pairs:', brute_pairs(n), 'pointer steps at most:', n - 1)

Edge cases and pitfalls

Two walls form exactly one container. The loop scores that pair once and ends. Walls of equal height move the right pointer in this version, and either move is safe because the level cannot rise while the gap shrinks.

Moving the taller wall is the central pitfall. The level stays capped by the shorter wall. The gap only shrinks, so every later container with that pair of ends is worse.

def max_area(heights):
    left = 0
    right = len(heights) - 1
    best = 0
    while left < right:
        area = (right - left) * min(heights[left], heights[right])
        if area > best:
            best = area
        if heights[left] < heights[right]:
            left += 1
        else:
            right -= 1
    return best

print('two walls:', max_area([1, 1]))
print('all equal:', max_area([3, 3, 3, 3]))
print('falling:', max_area([5, 4, 3, 2, 1]))
print('zero walls:', max_area([0, 0, 0]))
print('one tall middle:', max_area([1, 9, 1]))