# 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 $O(n)$ 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. $h(i)$ indicates the height of the vertical line $i$.
2. $L$ is the left pointer. $R$ is the right pointer.
3. $A(i,j)$ is the amount of water between vertical lines $i$ and $j$.

## Plan

General Approach

Assume that there is a unique optimal solution $(i^*, j^*)$ and show that the algorithm can find $(i^*,j^*)$ 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 $h(i^*) \le h(j^*)$. Then consider the following cases:

1. $L$ hits $i^*$ before $R$ hits $j^*$
2. $L$ hits $j^*$ before $R$ hits $i^*$
3. $R$ hits $i^*$ before $L$ hits $j^*$
4. $R$ hits $j^*$ before $L$ hits $i^*$

We will show that in any of these cases, the algorithm will continually move the other pointer that is neither at $i^*$ nor at $j^*$ 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, $L$ hits $i^*$, so we aim to show that the algorithm will immediately move $R$ towards $j^*$ until it hits $j^*$. Then we have shown that the algorithm finds $(i^*, j^*)$ 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 $(i^*, j^*)$ in general.

## Formal Proof

Suppose $L$ hits $i^*$ before $R$ hits $j^*$. Let $j$ denotes the vertical line that is currently being pointed by $R$. Since $L$ hits $i^*$ before $R$ hits $j^*$, we have that $j > j^*$ at this moment. Then we claim that $h(j) < h(i^*)$.

Claim

$h(j) < h(i^*)$.

Proof

Suppose for contradiction that $h(j) \ge h(i^*)$. Since $j-i > j-i^*$ and the $y$-value is determined by the shorter line, i.e., $h(i^*)$ in both case, so $A(i^*, j) > A(i^*, j^*)$, contradiction to the optimality of $(i^*, j^*)$.

By the design of our algorithm and the above claim, $R$ will move to $j^*$.

## Idea Illustration

This drawing assists you to understand the argument. Here, under our assumption, $h(j) \ge h(i^*)$, 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, $R$ will move inward until it hits $j^*$.

## 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.