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.