I was solving a coding problem where:

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

https://leetcode.com/problems/container-with-most-water/description/

My answer used brute force but the suggested answer with a time complexity of O(n) was this:

var maxArea = function (height) {
  let biggestArea = Number.MIN_VALUE;
  let leftPointer = 0;
  let rightPointer = height.length - 1;

  while (leftPointer < rightPointer) {
    let leftHeight = height[leftPointer];
    let rightHeight = height[rightPointer];
    let heightToUse = leftHeight < rightHeight ? leftHeight : rightHeight;
    let area = heightToUse * (rightPointer - leftPointer);
    biggestArea = Math.max(biggestArea, area);

    if (leftHeight < rightHeight) {
      leftPointer  ;
    } else {
      rightPointer--;
    }
  }

  return biggestArea;
};

I understand how this solution works but I still dont understand how the two-pointer technique eliminates the need to check every element with every element. could someone please explain the logic behind it? thank you.

CodePudding user response：

how the two-pointer technique eliminates the need to check every element with every element

When you have a pair (leftPointer, rightPointer), then the least of height[leftPointer] and height[rightPointer] determines the volume that the corresponding container has.

Let's assume that height[leftPointer] is the lesser one (or at least not greater).

Then we know that for any i in the range [leftPointer 1, ..., highPointer] the volume between leftPointer and i cannot be greater than what we already have. Even if there would be a very high height[i] it wouldn't matter as then height[leftPointer] is the lesser and determining height. And because the distance between leftPointer and i is less than the distance between leftPointer and rightPointer, the volume can never exceed what we already have.

So we don't need to visit those leftPointer, i pairs. That's were we avoid making all combinations.

On the other hand, we cannot exclude that there is an i where the i, highPointer pair would represent a greater volume container. That is why leftPointer is the correct action to take, and then the same reasoning can be applied to the new pair.