Container With Most Water

Abstract

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.

Preparation

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.

Notations

We will use the following notations:

  1. indicates the height of the vertical line .
  2. is the left pointer. is the right pointer.
  3. is the amount of water between vertical lines and .

 

Plan

General Approach

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.

 

Case Studies

Assume without loss of generality that . Then consider the following cases:

  1. hits before hits
  2. hits before hits
  3. hits before hits
  4. hits before hits

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.

 

Formal Proof

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 .

Claim

.

Proof

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 .

 

Idea Illustration

image-20191229203118750

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 .

image-20191229203812060

Exercise

It turns out that the other cases are analogous to the first case, so leave the proof of the remaining cases as an exercise.