In this article, we will talk about the 11-th LeetCode question, i.e. container with most water. Specifically, we will focus on the correctness of the algorithm provided under its corresponding LeetCode solution tag.
First off, if you have not familiarized yourself with this question in LeetCode and/or its official O(n) solution, please do so by accessing this link.
We will use the following notations:
Assume that there is a unique optimal solution and show that the algorithm can find so that it should be clear that when there are multiple optimal solutions, the algorithm will find at least one of them.
Assume without loss of generality that . Then consider the following cases:
We will show that in any of these cases, the algorithm will continually move the other pointer that is neither at nor at to one of them that has not been hit by the first pointer that reaches one of the targets. For example, let's say we are in the first case and, now, hits , so we aim to show that the algorithm will immediately move towards until it hits . Then we have shown that the algorithm finds in the first case. If we can prove that the algorithm behaves in such a manner in any of these cases, it should be clear that the algorithm can find in general.
Suppose hits before hits . Let denotes the vertical line that is currently being pointed by . Since hits before hits , we have that at this moment. Then we claim that .
Suppose for contradiction that . Since and the -value is determined by the shorter line, i.e., in both case, so , contradiction to the optimality of .
By the design of our algorithm and the above claim, will move to .
This drawing assists you to understand the argument. Here, under our assumption, , and therefore we get an area that is larger than the optimum. Thus, this gives us a contradiction.
We know that the algorithm will always move inward the pointer that points to the shorter line. Therefore, will move inward until it hits .
It turns out that the other cases are analogous to the first case, so leave the proof of the remaining cases as an exercise.