Container with Most Water
Tags: rust, algorithms, compsci, leetcode
Published: 2020-06-11 19:38:17

---
canonical_url: https://steadbytes.com/blog/container-with-most-water/
description: A solution and, importantly, a proof for LeetCode Problem 11 - Container with Most Water.
published: true
tags:
- Rust
- Algorithms
- CompSci
- LeetCode
title: Container with Most Water
---

> This post originally appeared on [steadbytes.com](https://steadbytes.com/blog/container-with-most-water/) 
<div></div>

A solution and, importantly, a proof for LeetCode Problem 11 - [Container with Most Water](https://leetcode.com/problems/container-with-most-water/).
<!--more-->

This problem intrigued me as, unlike many "LeetCode-esque" problems, little advanced or specific algorithms theory is required for an optimal {% katex inline %} O(n) {% endkatex %} 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 {% katex inline %} n {% endkatex %} non-negative integers {% katex inline %} a_{1}, a_{2}, ..., a_{n} {% endkatex %} , where each represents a point at coordinate {% katex inline %} (i, a_{i}) {% endkatex %}. {% katex inline %} n {% endkatex %} vertical lines are drawn such that the two endpoints of line {% katex inline %} i {% endkatex %} is at {% katex inline %} (i, a_{i}) {% endkatex %} and {% katex inline %} (i, 0) {% endkatex %}. 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 {% katex inline %} n \geq 2 {% endkatex %}
>
> &mdash; <cite>https://leetcode.com/problems/container-with-most-water </cite>

**Example**:

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

![Example Graph](https://steadbytes.com/container-with-most-water-example.png)

## Solution

```rust
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 {% katex inline %} O(n) {% endkatex %}. 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](https://steadbytes.com/container-with-most-water-key-idea-visualisation.png)

## Proof

### Definitions

Let {% katex inline %} a_{i} {% endkatex %} be the height of the line at index {% katex inline %} i {% endkatex %} and {% katex inline %} W(i, j) {% endkatex %}, {% katex inline %} H(i, j) {% endkatex %}, {% katex inline %} A(i, j) {% endkatex %} be the width, height and area, respectively, formed by the container between {% katex inline %} a_{i} {% endkatex %} and {% katex inline %} a_{j} {% endkatex %}:

{% katex %}  W(i, j) = i-j  {% endkatex %}

{% katex %}  H(i, j) = min(a_{i}, a_{j})  {% endkatex %}

{% katex %}  A(i, j) = W(i, j) \cdot H(i,j) {% endkatex %}

### Loop Invariant

> The "key idea" previously mentioned.

_Hypothesis_: For any {% katex inline %} i, j {% endkatex %} where {% katex inline %} i< j {% endkatex %}, {% katex inline %} A(i, j) {% endkatex %} is greater than the area produced by moving either {% katex inline %} j {% endkatex %} _towards_ {% katex inline %} i {% endkatex %} if {% katex inline %} a_{i} < a_{j} {% endkatex %} or {% katex inline %} i {% endkatex %} towards {% katex inline %} j {% endkatex %} otherwise:

{% katex %} \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} {% endkatex %}

When {% katex inline %} a_{i} < a{j} {% endkatex %}:

{% katex %} i^\prime=i {% endkatex %}

{% katex %} j^\prime = j - 1 {% endkatex %}

The container width, by definition, has decreased since {% katex inline %} j {% endkatex %} has moved closer to {% katex inline %} i {% endkatex %}:

{% katex %} W(i, j^\prime) < W(i, j) {% endkatex %}

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

{% katex %} a_{i} \geq a_{j^\prime} \Rightarrow  H(i, j^\prime) = a_{j^\prime} \leq H(i, j) {% endkatex %}

{% katex %} a_{i} < a_{j^\prime} \Rightarrow  H(i, j^\prime) = a_{i} < H(i, j) {% endkatex %}

{% katex %} \Rightarrow H(i, j') \leq H(i, j) {% endkatex %}

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

The same process applies to the case where {% katex inline %} a_{i} > a_{j} {% endkatex %}.

### 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`:

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

The loop contains and `if`-`else` expression which defined the _only two_ possible code paths:

```rust
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:

```rust
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 {% katex inline %} l {% endkatex %} and {% katex inline %} r {% endkatex %}, each iteration of the `while` produces new values of {% katex inline %} l {% endkatex %} and {% katex inline %} r {% endkatex %} as follows:

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

Since {% katex inline %} l {% endkatex %} and {% katex inline %} r {% endkatex %} are initialised to {% katex inline %} 0 {% endkatex %} and {% katex inline %} n {% endkatex %}, where {% katex inline %} n > 0 {% endkatex %}, the two values converge and thus loop exit condition {% katex inline %} l < r {% endkatex %} is satisfied.