Red-Green-Code

Problem

LeetCode 11: Container With Most Water (Medium)

Problem Statement: In the coordinate plane, consider $n$ vertical lines starting at points $(1, 0), (2, 0), …, (n, 0)$ and ending at points $(1, h_1), (2, h_2), …, (n, h_n)$, where each $h_i$ is a non-negative integer. We can construct a rectangle whose sides are the $x$-axis, two of these vertical lines, and a horizontal line connecting $(i, h_i)$ and $(j, h_i)$ for some $i$ and $j$ where $h_i < h_j$. Return the maximum possible area of such a rectangle.

The statement above is an alternate way of expressing the original problem, which is described in terms of a container filling with water. For a visual representation, see the problem page on LeetCode.

Solution

This problem can be solved using a simple $O(n)$ algorithm, as explained by several people in the discussions, including Stefan Pochmann. But finding that algorithm and understanding why it’s correct isn’t as simple. Let’s take it step by step.

We’re trying to maximize the area of a rectangle, $A = height \times width$. To get the maximum width, we would need to use the first and last vertical lines, at $x$ coordinates $1$ and $n$. This gives us a width of $w = n-1$ and a height of $h = min(h_1, h_n)$. If $h$ happens to be the maximum height, then we’re done. But there’s no way to know that without checking smaller widths.

The only way to get a larger rectangular area with a smaller width is to increase the height. Consider two line heights, $h_i$ and $h_j$, where $h_i < h_j$. The area of the rectangle that uses these two lines is $A = h_i \times |j-i|$, since we’re required to use the smaller of the two heights.

To use a longer line, we have to discard either $h_i$ or $h_j$. Which one should we discard? As long as we include $h_i$ in our rectangle, we can’t get an area any larger than $A$, since the rectangle height will be at most $h_i$, regardless of which line we pair it with. Therefore, the only way to find a larger area is to discard $h_i$ and keep $h_j$. (In the case where $h_i = h_j$, we can discard either one).

This is the key idea for the algorithm: At each step, discard the smaller line and keep the larger one. If we start with a left pointer $i=1$ and a right pointer $j=n$, then at each step we either increment $i$ or decrement $j$, depending on which line is smaller. When the pointers meet, we have checked all $n$ lines, and no line has been checked more than once, so we have an $O(n)$ algorithm.

Pseudocode

For the pseudocode, we’ll switch to 0-based indexing, since that’s how the input data is stored.

Variables:

• height[]: Input data, consisting of $n$ integer heights
• i: Left pointer, starting at $0$
• j: Right pointer, starting at $n-1$
• minh: The smaller of the two heights
• area: The current area

• max: The maximum area found so far

  while i < j
      minh = minimum of height[i] and height[j]
      area = minh * j-i
      if area > max, update max
  
      if height[i] < height[j] then i++
      else j--
  
  return max
  

The algorithm: As long as the pointers haven’t crossed, we calculate the current area and see if we have a new maximum. Then we either increment the left pointer or decrement the right pointer, depending on the relative heights. Once we make it through the input, we return the maximum area found.

Code

Container With Most Water on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.