LeetCode problem #11 — Container with most water (JavaScript)

In this LeetCode challenge we’re given a series of column heights, and asked to find the largest volume of water that will fit between two columns without spilling.

In other words, if you have 2 columns, of heights 3 and 5, and they are spaced 2 units apart, how much water can fit in them? Well, the highest you can go is 3 (as otherwise the water would spill out), and the width is 2, so the area is 2 x 3 which is 6.

Solution 1: Double loop

This is the brute force approach, and it is very inefficient.

First we loop through all available columns. Then, for each column, we loop from this point forwards, looking at each and every subsequent column, and calculating the potential area for each. At each iteration, we check if we’ve found the new biggest available area, and store it if so.

Solution #2: Left and right pointers

This approach is based on a fairly simple concept: If we start at the left-most and right-most points (0 and length minus 1 respectively), and move only the smaller of the two points inwards, we will eventually find the highest available area.

The reason this works is that if our left-marker is at a height of 5, and our right-marker is at a height of 3, then moving the left-marker (5) inwards is redundant, as we will be limited by the right-height (3) anyway, and therefore can only find a smaller area. Here it is in practise:

This approach is much faster, as it only involves a single loop.