Solution to LeetCode Container with most water problem.

The naive version would solve this in \(O(n^2)\) time. It can be improved as follows to linear time:

Keep two indices \(i\) and \(j\), that start on both ends of the array to process, `height`

. Our final goal is to find \(i\),\(j\), such that \[
A(i,j) = (j-i) \times \min(\mathrm{height}(i), \mathrm{height}(j))
\] is maximized. At every step, if `height[i] < height[j]`

, move `i`

up by one. Otherwise move `j`

down by one, until the two pointers meet. We now show that this gives the maximal answer. Suppose we just computed \(A(i,j)\), and `height[i] < height[j]`

. If we increase \(i\) by one, we will ignore all the values \(A(i,k)\) for \(i \leq k \lt j\). We now show that \(A(i,j) \gt A(i,k)\). Since `height[i] < height[j]`

, \(A(i,k)\) is bounded by the `height[i]`

term, and since \(k < j\), it follows that \(A(i,j) \gt A(i,k)\), and we can safely ignore all of the \(A(i,k)\) and move on to inspecting \(A(i+1,j)\). The case with `height[i] > height[j]`

is symmetric.