cconnected.
Understand the pattern. Find your own way.Find your starting point
Your learning feed/Idea 22 of 218
Ideas this builds on
Arrays, search & sorting22 / 218

Container With Most Water

Picture

Lines of heights [1,8,6,2,5,4,8,3,7] form containers. Two chosen lines hold width times the shorter height.

Predict

Why keep the taller wall when shrinking the width?

Walk through the small example

Moving it cannot beat the same short wall. At the widest remaining pair, the shorter wall is the only side whose replacement might raise the limiting height.

Mental model and complete Python solution

Area is width times the lower wall. Once that lower wall is fixed, every inward partner is narrower and no taller container is possible with it. Discard that wall.

What the function promises: Return the maximum area. Heights are nonnegative integers; fewer than two lines return zero.

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

assert max_water([1,8,6,2,5,4,8,3,7]) == 49
assert max_water([5]) == 0

Work and storage: O(n) time and O(1) extra space.

When to recognize it: At the widest remaining pair, the shorter wall is the only side whose replacement might raise the limiting height.

Check before applying it: Moving pointers based on a tempting local area without the shorter-wall proof can discard the optimum.

Change one rule

Now the walls have different horizontal gaps.

See what changes

Use their actual coordinates for width. The same dominance proof works if coordinates are ordered.

Connect

Two pointers: shrink one search space: Reuse ordered elimination even though the heights are not sorted.

greedy proof: The discarded alternatives need a dominance argument.