Container With Most Water
Given heights of vertical lines on the x-axis, pick two lines that together with the axis hold the most water.
Open on LeetCode ↗Intuition
The instinct is to move whichever pointer sits at the taller line, because taller feels like the side worth keeping. It is exactly backwards. The area is bounded by the SHORTER of the two lines, so moving the taller one can never help: the width shrinks by one and the height is still capped by the short side you kept, which means every such pair is strictly worse than the one you just measured. Take [1, 8, 6, 2, 5, 4, 8, 3, 7] — at the start the left line is 1, and no partner in the entire array can lift that pair above 1 × 8, so index 0 is dead the moment you have measured it once. Move the shorter pointer and you at least give yourself the chance of a taller wall on that side. That is the invariant: everything you discard was already dominated by the pair you just computed, so a single O(n) sweep is allowed to skip the other O(n^2) pairs without ever looking at them.
Approach
Start at the extremes
Put one pointer at index 0 and the other at the last index. This is the widest container available, and width only ever decreases as the pointers converge — so it is the natural baseline. Any pair found later has to win on height, because it has already lost on width. Record its area as the running best.
Measure, then retire the shorter line
The area of the current pair is min(h[lo], h[hi]) multiplied by (hi - lo). Compute it, update the maximum, then advance the pointer sitting at the shorter line. The justification is a domination argument: for the shorter line, the pair you just measured is the best it will ever achieve, since every remaining partner is closer (less width) and the height stays clamped by that same short line. So the line can be discarded outright, together with every untested pair that used it.
Converge and return the max
Repeat until the pointers meet. Each iteration permanently eliminates one line, so the loop runs at most n - 1 times and the whole search is O(n) with O(1) extra space. The answer is the largest area seen along the way; nothing better was skipped, because every skipped pair was eliminated by a proof, not by a heuristic.
Solution & live demo
Edge cases
The loop runs once, measures min(h[0], h[1]) * 1, and the pointers immediately meet. That single area is the answer.
Neither side dominates, so either may be moved; the code moves the left one. Both choices are safe because the pair has already been measured and both lines are equally capped.
The left pointer is always the shorter and advances every time, so the sweep degenerates to a simple left-to-right walk and still finds the true maximum.
It contributes area 0 and is the shorter side, so it is retired on the very next move without any special-casing.