11. Container With Most Water

You are given an integer array height of length $n$. There are $n$ vertical lines drawn such that the two endpoints of the $i^{th}$ line are $(i, 0)$ and $(i, h[i])$.

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

Where would a good place be to start with this problem? The brute force solution would require us to check every combination of indices and finding the maximum volume that way. Instead, let’s start with just how water volume is calculated here. Let $v(i, j)$ be the volume of water held by the container formed by the line at the $i$th index and the $j$th index, where

The equation gives us some clues on where to start: it is made of 2 parts, $\min(h[i], h[j])$ and $|i - j|$.

1. $|i - j|$ is the distance between $i$ and $j$: so to maximise it, we should first look at the indices that are the furthest apart, $(0, n)$.
2. $\min(h[i], h[j])$ tells us that the limiting factor for volume is whichever line is shorter. Therefore to improve on $v(i, j)$, we should replace whichever is smaller with a line that is bigger.
3. $v(i, j)$ is symmetrical: $v(i, j) = v(j, i)$.

Combined, our strategy takes shape: first start at the ends of the array, and continuously replace whichever line is shorter with the next line closer to the center, and repeat until the ends meet. We don’t have to check past that since the volume equation is symmetrical.

def maxArea(self, height: List[int]) -> int:
	l, r = 0, len(height) - 1
	max_vol = 0
	
	while l < r:
		volume = min(height[l], height[r]) * (r - l)
		max_vol = max(max_vol, volume)
		if height[l] < height[r]:
			l += 1
		else:
			r -= 1
	
	return max_vol

Let’s say $\min(h[i], h[j]) = h[i]$. When we move to $h[i + 1]$, we are essentially discarding all the pairs $(i, i + 1), \dotsc, (i, j - 1)$ as not the optimal solution. How can we be so sure?

Consider one of those indices $k \in \{i + 1, \dotsc, j - 1\}$. First, notice that $|i - k| < |i - j|$, so for $v(i, k)$ to be the optimal solution we must have $\min(h[i], h[j]) < \min(h[i], h[k])$.

• If $\min(h[i], h[k]) = h[i]$, then $\min(h[i], h[k]) = \min(h[i], h[j])$, so $v(i, k) < v(i, j)$.
• Otherwise, $\min(h[i], h[k]) = h[k]$, so $h[k] \leq h[i] = \min(h[i], h[j])$. Thus $v(i, k) < v(i, j)$.

Either way, none of those indices can be the optimal solution, so we are safe to discard them.

Time Complexity

Notice that l and r start at the ends of the array, and move towards each other one at a time. Since the while loop terminates when l >= r, the while loop iterates $n$ times. Each iteration is constant time, and since lines 1 and 2 as well as the return statement are constant time as well, the runtime complexity is in $\mathcal{O}(n)$.

Space Complexity

The only space used is to store l, r, max_vol, and volume, which are all constant integers—thus the space complexity is constant, in $\mathcal{O}(1)$.