Container With Most Water

Problem

Given an array of non-negative integers representing line heights, find two lines that together with the x-axis form a container holding the most water. Return the maximum area.

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]  → 49  (lines at index 1 and 8)
Input: [1, 1]                         → 1
Input: [4, 3, 2, 1, 4]               → 16  (lines at index 0 and 4)

Solution

Approach - opposite-ends two pointers, always move the shorter side.

Start with the widest possible container: left at index 0, right at the last index. The area is min(height[left], height[right]) * (right - left) - the shorter wall caps the height, and the gap is the width. Each step you record this area against best, then move one pointer inward. The decision of which to move is the whole problem: you always advance the pointer at the shorter line.

The reason this never misses the optimum is a discard argument. The current width is the largest it will ever be for any pair involving these two walls, since moving either pointer inward only narrows it. The shorter wall caps the area no matter how tall its partner is, so any other pair that still uses that shorter wall can only be narrower and therefore worse. That means the shorter wall has nothing left to offer - you can safely abandon it and never revisit it. Moving the taller wall instead would keep the same height cap while shrinking width, which can only lose area. Trace [1, 8, 6, 2, 5, 4, 8, 3, 7]: the pair at indices 1 and 8 gives min(8, 7) * 7 = 49, the maximum.

Edge cases - when the two heights are equal, both are the limiting side; moving either is correct (the code moves left). The two-element case [1, 1] yields the single container min(1, 1) * 1 = 1. No sorting is needed - the rule compares only current heights.

Complexity - O(n) time, O(1) space - the pointers move inward a combined n times, tracking three scalars.