Proof of Leetcode 11 "Container with most water"

The solution to Leetcode “Container with most water” is a classic two-pointer/greedy algorithm. It sets up the two pointers at the left-most and right-most bar. Then, at each time, it moves the pointer previously pointing to the lower bar to the middle; during the process, records the results of reaching a higher bar, and finally stops and update the pointer position at a bar higher than the one pointed by the other pointer. It stops when left+1 == right.

As with most of the greedy algorithms, the correctness of solution is nontrivial. So here is a simple proof by analysis to show the logic of this design.

Let’s mark the bars with different type:

• a for non-checked bars.
• b2 for checked, but not used as final-pointer-location bars.
• b1 for the final-pointer-location bars for each round.

Here we consider one round of “first move right against left, and then move left against right”:

Denote the container configurations as (x, y), and for convenience use < to indicate a larger container of the right side.

During this round, we have recorded all the containers of configurations (b1, b1), (b1, b2) and (b2, b1).

So we need to prove if the non-recorded configurations will have a larger container than the recorded ones. Now we prove this for the different cases:

So the conclusion is that, for those non-recorded cases, we can always find one recorded case to upper-bound it. So chaining the rounds we will make sure the algorithm has the optimal solution in its search.