The Container with the Most Water: Solving an Algorithm about Areas

Today's algorithm is the Container with the Most Water:

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (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 n is at least 2.

This is one of the problems on Leetcode that is phrased in a very complicated way, and definitely requires an example to go along with it. Let's say you were given the array [1,8,6,2,5,4,8,3,7]. Placing each of these numbers on a bar chart, you'd get:

When the problem asks for the "container with the most water", it means that if you drew a horizontal line between any two of the vertical bars in this chart, which one would have the largest area. In other words, if these bars held rectangular containers of water, which container would be the largest? In the below graph, the container held by the two red bars would be largest:

In this post, I'll break down how to approach this problem, and then will solve it using JavaScript.

Approaching the problem

One way to approach this problem is to check every pair of heights in the given array, determine the area between them, and return the one with the largest area. While this "brute force" solution would give us the right answer, it's not optimized. We therefore should find a way to only check some of the lines, and the area between them.

According to the instructions, the container of water must be rectangular--that is, there can't be a slanted line on one of the sides. That means that the height of the largest container is determined by a line that's not necessarily the tallest.

Let's look at the first example again: the height of the container with the most water is determined by the line that's 7 units long, not by the line that's 8 units long.

This gives us a clue to how we're going to solve this problem. We want to always be checking two lines at the same time--we can call one the "left" line, and one the "right" line. We can find whichever one is smaller, left or right, and then find the area between those two lines. We will keep track of these two lines with two pointers, left, which points at the left line, and right, which points at the right line.

We'll start by having left at the first line, and right at the last line, and will create a loop that keeps checking the lines as long as left is less than right. We'll find the area between those two lines, and then we can decide whether we want to move the left pointer toward the center, or the right pointer toward the center. If the left line is smaller than the right line, then there may be a line further on in the array that's taller and would produce a larger area; therefore, we'd want to increment the left pointer. If the right line is smaller than the left line, then there may be a line earlier on in the array that's taller and would produce a larger area; therefore, we'd want to decrement, or decrease by 1, the right pointer.

Solving the algorithm

To start, we'll initialize a few variables. max will store the maximum area, which we will return at the end. left is the left pointer, which will start at the index 0. right is the right pointer, which will start at the last element in the inputted array, height.

function maxArea(height) {
  let max = 0;
  let left = 0;
  let right = height.length - 1;

  //...
  return max;
}

Now, we'll create a while loop that will keep going as long as left is less than right. We can access the line that the left variable is pointing to with height[left], and the line that the right variable is pointing to with height[right]. We want to know which one is smaller, so inside the while loop, we'll create a variable called smallerLine. smallerLine will use the Math.min() method, which returns the smaller of two integers. We will pass in the left and right line.

function maxArea(height) {
  let max = 0;
  let left = 0;
  let right = height.length - 1;

  while (left < right) {
    let smallerLine = Math.min(height[left], height[right]);
    //...
  }
  return max;
}

Now, we want to see if the area between the two lines is larger than the current max area that we've found. To check this, we can use Math.max(), and pass in the current max, as well as smallerLine * (right - left). The area of a rectangle is calculated by multiplying height by width. The height is determined by smallerLine, and the width is the distance between the right and left pointers. We'll set max equal to whichever value is larger.

function maxArea(height) {
  let max = 0;
  let left = 0;
  let right = height.length - 1;

  while (left < right) {
    let smallerLine = Math.min(height[left], height[right]);
    max = Math.max(max, smallerLine * (right - left));
    //...
  }
  return max;
}

If the left line is smaller than the right line, then we'll want to increment the left variable. Otherwise, we'll want to decrement the right variable. At some point, left will no longer be smaller than right, and the while loop will finish running. When that happens, the function will return max, which contains the maximum area found.

function maxArea(height) {
  let max = 0;
  let left = 0;
  let right = height.length - 1;

  while (left < right) {
    let smallerLine = Math.min(height[left], height[right]);
    max = Math.max(max, smallerLine * (right - left));
    if (height[left] < height[right]) {
      left++;
    } else {
      right--;
    }
  }
  return max;
}

--

Please let me know if you have any questions or alternate ways of solving this problem!