Container with Most Water

A solution and, importantly, a proof for LeetCode Problem 11 - Container with Most Water.

This problem intrigued me as, unlike many “LeetCode-esque” problems, little advanced or specific algorithms theory is required for an optimal O(n)O(n) solution. That is, there was no algorithmic or mathematical trick that one needed to solve the problem. Instead, the solution relies on a subtle insight that leads to a relatively simple algorithm. This, in my opinion, is the real skill behind designing algorithms that can be gained from “LeetCode-esque” problems - as opposed to re-writing the same handful of algorithms over and over again.

The algorithm itself is fairly simple to understand intuitively, however understanding why it works is less so. In this article, I present my solution (which is essentially identical to many others you may find) and provide a formal proof of the key insight; something I have been unable to find a satisfactory example of.

I encourage the reader to visit LeetCode and attempt to solve the problem before reading further.

Problem

Given nn non-negative integers a1,a2,...,ana_{1}, a_{2}, ..., a_{n} , where each represents a point at coordinate (i,ai)(i, a_{i}). nn vertical lines are drawn such that the two endpoints of line ii is at (i,ai)(i, a_{i}) and (i,0)(i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n2n \geq 2

https://leetcode.com/problems/container-with-most-water

Example:

Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49

Example Graph

Solution

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        let mut l = 0;
        let mut r = height.len() - 1;
        let mut max_area = 0;

        while l < r {
            let width = (r - l) as i32;
            if height[l] < height[r] {
                max_area = max(max_area, height[l] * width);
                l += 1;
            } else {
                max_area = max(max_area, height[r] * width);
                r -= 1;
            }
        }
        max_area
    }
}

Using two pointers, the entire array of heights is processed in a single pass from both ends simultaneously; thus O(n)O(n). On each iteration, the area of the container between l and r is calculated and the lower-heighted of the two is moved towards the other. Either can be moved in the case that i == j (so long as it is consistent) - here I chose to move r. The maximum are

The key idea is that for any two positions of l and r, the corresponding container area is larger than that of any container produced by moving the pointer with the larger height towards the other. All such containers therefore need not be considered.

Key Idea Illustration

Proof

Definitions

Let aia_{i} be the height of the line at index ii and W(i,j)W(i, j), H(i,j)H(i, j), A(i,j)A(i, j) be the width, height and area, respectively, formed by the container between aia_{i} and aja_{j}:

W(i,j)=ij W(i, j) = i-j

H(i,j)=min(ai,aj) H(i, j) = min(a_{i}, a_{j})

A(i,j)=W(i,j)H(i,j) A(i, j) = W(i, j) \cdot H(i,j)

Loop Invariant

The “key idea” previously mentioned.

Hypothesis: For any i,ji, j where i<ji< j, A(i,j)A(i, j) is greater than the area produced by moving either jj towards ii if ai<aja_{i} < a_{j} or ii towards jj otherwise:

{max(A(i,j),...,A(i,i+1))if ai<ajmax(A(i,j),...,A(j1,j))else\begin{cases}max(A(i, j),...,A(i, i+1)) &\text{if $a_{i} < a_{j}$}\\max(A(i,j),...,A(j-1, j)) &\text{else}\end{cases}

When ai<aja_{i} < a{j}:

i=ii^\prime=i

j=j1j^\prime = j - 1

The container width, by definition, has decreased since jj has moved closer to ii:

W(i,j)<W(i,j)W(i, j^\prime) < W(i, j)

Since ai<aja_{i} < a_{j}, there are two cases for the height of the container H(i,j)H(i, j^\prime):

aiajH(i,j)=ajH(i,j)a_{i} \geq a_{j^\prime} \Rightarrow H(i, j^\prime) = a_{j^\prime} \leq H(i, j)

ai<ajH(i,j)=ai<H(i,j)a_{i} < a_{j^\prime} \Rightarrow H(i, j^\prime) = a_{i} < H(i, j)

H(i,j)H(i,j)\Rightarrow H(i, j') \leq H(i, j)

Thus, A(i,j)<A(i,j)by definition of (A)A(i, j^\prime) < A(i, j) \quad \text{by definition of (A)}

The same process applies to the case where ai>aja_{i} > a_{j}.

Termination

Since the result is returned immediately after exiting the single while loop, proving termination is equivalent to proving the termination of this loop.

The while loop terminates when the expression l < r evaluates to false:

while l < r {
    // ...
}
// l >= r

The loop contains and if-else expression which defined the only two possible code paths:

while l < r {
    let width = (r - l) as i32;
    if height[l] < height[r] {
        max_area = max(max_area, height[l] * width);
        l += 1; // 1.
    } else {
        max_area = max(max_area, height[r] * width);
        r -= 1; // 2.
    }
}

The lines indicated 1. and 2. are the only lines that affect the while loop condition - calculations of width and max_area do not alter the values of l and r. Therefore, there are two relevant cases:

while l < r {
    if some_condition {
        l += 1;
    } else {
        r -= 1;
    }
}

Either, l is incremented or r is decremented. Since l is initialised to 0 and r to the length of the height array the two must converge and thus the while loop must terminate.

More formally, with respect to pointers ll and rr, each iteration of the while produces new values of ll and rr as follows:

(l,r)={(l+1,r)if ai<aj(l,r1)else(l^\prime, r^\prime) =\begin{cases}(l + 1, r) &\text{if $a_{i} < a_{j}$}\\\\(l, r - 1) &\text{else}\end{cases}

Since ll and rr are initialised to 00 and nn, where n>0n > 0, the two values converge and thus loop exit condition l<rl < r is satisfied.

comments powered by Disqus