Greedy Pointer Elimination

Foundations

So far, each comparison told the pointers what to do: a pair matched or it did not, and a sum was too small or too big. Now, what if there is no goal to compare against, only the best pair to find, so every move needs a reason of its own?

Score each pair of indexes i < j as the distance j - i times its minimum, min(nums[i], nums[j]). Start with the pair farthest apart, left = 0 and right = n - 1. Every other pair is closer, so it can only win with a larger minimum, and the end holding the smaller value can never give one: every pair it still forms is capped by it. Score the pair, then drop that end.

On nums = [7, 1, 5, 3, 6], the first pair, indexes 0 and 4, scores 4 × min(7, 6) = 24, and nums[4] = 6 is its smaller end, so index 4 goes. The next pairs score 9, 10, and 1, each dropping its smaller end, and the best stays 24. Four scores stand in for all 10 pairs, and every skipped pair was proven no better.

Case Scenario

Container With Most Water draws that score. height[i] is a vertical line at position i, and two lines plus the floor form a container: its width is the distance j - i, and the water can rise only to the shorter line, min(height[i], height[j]). In height = [1, 8, 6, 2, 5, 4, 8, 3, 7], the lines at indexes 1 and 8 hold 7 × 7 = 49, the most of any pair.

The direct approach measures every pair of lines with two nested loops: an outer loop fixes the left line i, and an inner loop pairs it with every line to its right. That is n(n - 1)/2 containers, 36 for these nine lines, and the loops cannot stop early, because any pair might be the best. Step through the passes below to see how many of those measurements never had a chance.