The Container with the Most Water: Solving an Algorithm about Areas
Tags: javascript, leetcode, algorithms, codenewbie
Published: 2020-08-28 18:34:36

Today's algorithm is the [Container with the Most Water](https://leetcode.com/problems/container-with-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:

![Bar chart for the numbers [1,8,6,2,5,4,8,3,7]](https://dev-to-uploads.s3.amazonaws.com/i/og2v216catoexf2d2s8n.png)

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:

![The second bar, 8, and the last bar, 7, are highlighted in red, and the rest of the bars are in black. The rectangular area between these two bars is in blue.](https://dev-to-uploads.s3.amazonaws.com/i/ec2nqqn4una3dh89sdvm.png)

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.

![The second bar, 8, and the last bar, 7, are highlighted in red, and the rest of the bars are in black. The rectangular area between these two bars is in blue. The width of the blue box is 7, and the height of the blue box is 7.](https://dev-to-uploads.s3.amazonaws.com/i/jknj1v9ijout9ipyur26.png)

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`.

```javascript
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.

```javascript
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.

```javascript
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.

```javascript
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!