DEV Community

Ben Steadman
Ben Steadman

Posted on • Originally published at steadbytes.com

Container with Most Water

This post originally appeared on steadbytes.com

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
Enter fullscreen mode Exit fullscreen mode

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
    }
}
Enter fullscreen mode Exit fullscreen mode

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)=ijW(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 AA(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
Enter fullscreen mode Exit fullscreen mode

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.
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (4)

Collapse
 
jaseemabid profile image
Jaseem Abid

I came up with something slightly different:

pub fn max_area(height: Vec<i32>) -> i32 {
    let mut best = 0;

    for left in 0..height.len() {
        for right in (left + 1)..height.len() {
            let width = (right - left) as i32;
            let height = height[left].min(height[right]);
            let volume = width * height;

            best = best.max(volume);
        }
    }

    best
}
Collapse
 
steadbytes profile image
Ben Steadman

This is correct, but have you considered the runtime complexity? What happens if a large input, say 10000 elements is provided?

Take a look at this playground for an example (it is likely to timeout so you may wish to copy the code and run it locally) :)

Collapse
 
benph profile image
Ben

This post really challenges my cynicism of leet-code style problems. "All tests pass" is the least interesting part, but seems to get the most focus. This one puts almost no focus on that, and really takes off when we get to the interesting stuff.

I'll be putting a bit of time into this one. Thanks!

Collapse
 
steadbytes profile image
Ben Steadman

Thanks Ben, I agree 100%. Unfortunately I think too much focus is put on the competitive side of these problems e.g. "how can I get the tests to pass as quickly as possible" or wrote memorisation of common solutions rather than the process of solving the problem and how/why an algorithm actually works.

Glad you're willing to take the time on my post - I hope you enjoy it!