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 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 non-negative integers , where each represents a point at coordinate . vertical lines are drawn such that the two endpoints of line is at and . 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
Example:
Input: [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49
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
. 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.
Proof
Definitions
Let be the height of the line at index and , , be the width, height and area, respectively, formed by the container between and :
Loop Invariant
The "key idea" previously mentioned.
Hypothesis: For any where , is greater than the area produced by moving either towards if or towards otherwise:
When :
The container width, by definition, has decreased since has moved closer to :
Since , there are two cases for the height of the container :
Thus,
The same process applies to the case where .
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
and
, each iteration of the while
produces new values of
and
as follows:
Since and are initialised to and , where , the two values converge and thus loop exit condition is satisfied.
Top comments (4)
I came up with something slightly different:
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) :)
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!
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!