LeetCode #11

Container With Most Water
This $O(n)$ solution is not intuitional. I proved recursively.

Proof

Let $K(i,j)$ be the water volume between $i$th line and $j$th line, $V(i,j)$be the largest water volume between $i$th line and $j$th line, and $a(i)$ be the height of the $i$th line.

$$V(i,j) = \max(K(i,j), V(i+1,j),V(i,j-1)$$

I want to delete either the second term or the third term since this calculation takes $O(n^2)$.

Proof.

Let $k,l$ be the lines which have most water between $i+1$th line and $j$th line.
Pattern 1. $(k,l)$ is included in $(i+1, j-1)$
Since $(i+1, j-1$) is included in $(i,j-1)$,$V(i,j-1)\ge V(i+1,j)$.

Pattern 2. $(k,l)$ is not included in $(i+1, j-1)$, which means that $l =j$
$a(i)\ge a(j) \Rarr K(i,j) \ge K(k,j) \Rarr K(i,j)\ge V(i+1,j)$.

Therefore, the second term can be deleted.

$$\begin{aligned} V(i,j) &= \max(K(i,j), V(i+1,j),V(i,j-1)) \\ &= \max(K(i,j), V(i,j-1)) \end{aligned}$$

This takes at most $O(n)$.

Q.E.D.