Container with most water (two pointers)

Medium TimeO(n) SpaceO(1)

Each value in height is a vertical line at that position. Two lines and the ground between them form a container: its width is the distance between them, and its height is the shorter of the two, because water spills over the lower side. Lines in between are ignored — they do not cut the container up. Return the largest area any pair can hold.

Examples

Example 1

Input
height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output
49
The 8 at index 1 against the 7 at index 8: min(8, 7) × (8 − 1) = 7 × 7.

Example 2

Input
height = [1, 1]
Output
1
min(1, 1) × (1 − 0) = 1, and there is only the one pair to try.

The Code

function maxArea(height) {
  let left = 0;
  let right = height.length - 1;
  let best = 0;
  while (left < right) {
    const area = Math.min(height[left], height[right]) * (right - left);
    best = Math.max(best, area);
    if (height[left] < height[right]) left++;
    else right--;
  }
  return best;
}
maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]);
Done
Step through maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) call by call

More like this

All two pointers examples (9) →