Derusting logic #02: Container With Most Water

After solving the first exercise of the series, I stayed on LeetCode to work on logic without asking for a ready-made solution. Challenge 011 is Container With Most Water.

We get an array of heights and need to pick two lines that form the container with the largest area.

How to compute the area

If I pick positions left and right, the width is the distance between them. The container height is limited by the shorter of the two lines.

area = min(left height, right height) × distance

For example, with these heights:

[1, 8, 6, 2, 5, 4, 8, 3, 7]

The lines at positions 1 and 8 have heights 8 and 7. The shorter height is 7, and the distance between them is 7. That combination produces an area of 49.

My first attempt

I started with two pointers, one at each end of the array. After computing the current area, I simulated two possibilities:

• advancing the left pointer;
• moving the right pointer back.

I computed the area of the next two pairs and picked the larger one. The main excerpt was this:

const paddingLeftArea =
  Math.min(heights[leftIndex + 1], heights[rigthIndex]) *
  (rigthIndex - leftIndex + 1);

const paddingRightArea =
  Math.min(heights[leftIndex], heights[rigthIndex - 1]) *
  (rigthIndex - 1 - leftIndex);

if (paddingLeftArea > paddingRightArea && paddingLeftArea > maxArea) {
  leftIndex += 1;
} else {
  rigthIndex -= 1;
}

The problem was in the hypothesis. The best local decision does not guarantee the best area over the rest of the array. I tried to guess the path by looking only at the next two moves. There was also an error in the distance formula of that draft: for a pair of positions, the width is right - left.

The observation that unlocks the problem

The area depends on two things: width and shorter height.

When the pointers are at positions left and right, moving the pointer of the taller line cannot raise the container’s minimum height. The width always shrinks, and the height limiting the area is still there.

So the pointer that must advance is the one at the shorter height. It is the only move that can find a taller line and make up for the lost width.

If the heights are equal, either one can advance. In the code, I chose to advance the left one when heights[leftIndex] <= heights[rigthIndex].

Two-pointer solution

/**
 * @param {number[]} heights
 * @return {number}
 */
var maxArea = function (heights) {
  let leftIndex = 0;
  let rigthIndex = heights.length - 1;
  let maxArea = 0;

  while (leftIndex < rigthIndex) {
    const minH = Math.min(heights[leftIndex], heights[rigthIndex]);
    const currentArea = minH * (rigthIndex - leftIndex);

    maxArea = Math.max(maxArea, currentArea);

    if (heights[leftIndex] <= heights[rigthIndex]) {
      leftIndex++;
    } else {
      rigthIndex--;
    }
  }

  return maxArea;
};

Each round, I compute the current pair’s area, update the largest area found, and move one of the pointers. The while loop converges toward the center and ends.

The advancing detail matters. In the version I had written, the pointers only advanced when the current area was not larger than maxArea. If a new maximum area was found, the same combination would be computed again, never leaving the loop. The fix was to separate the two decisions: record the area, then move the shorter-height pointer.

The result of the attempts

The LeetCode history looked like this:

• JavaScript: accepted, 3 ms and 63.6 MB.
• JavaScript: wrong answer.
• JavaScript: wrong answer.
• Go: accepted, 0 ms and 9.6 MB.
• TypeScript: accepted, 3 ms and 63.9 MB.
• Go: wrong answer.

There were three wrong-answer attempts before reaching the accepted solutions in JavaScript, Go, and TypeScript. More than counting submissions, I wanted to look at the error, understand the hypothesis that failed, and try again without outsourcing all the reasoning.

Complexity

The algorithm walks the array once. On each iteration, one of the pointers advances, so time complexity is O(n) and space complexity is O(1).

The first attempt also used two pointers but did extra work comparing future possibilities. The second solution uses a property of the problem to safely discard part of the combinations.

That was the exercise this time: not mistaking a choice that looks good now for a decision the problem actually lets you justify.

---

Derusting logic series #02 — Container With Most Water. Problem at leetcode.com/problems/container-with-most-water.