# LeetCode 11 – Container with most water

#### Posted on December 25, 2013

##### Last updated on December 25, 2013

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.

Markdown SHA1: 994892c26e396fe9e1378e71ddff5b876300c04d