Container With Most WaterMedium

Given an array of heights, height[i] is a vertical line at position i. Choose two lines that, together with the x-axis, form a container holding the most water. Return the max possible area.

Examples

Input: height = [1,8,6,2,5,4,8,3,7] → Output: 49

Approach

Checking every pair of lines works but is O(n²). Two pointers starting at both ends and moving inward gets it in one pass: the area is always limited by the SHORTER of the two lines, so moving the taller pointer inward can only shrink the width without any chance of increasing height — it can never help. Moving the shorter pointer, though, might find a taller line and increase the area. So always move the shorter side inward.

Complexity — best & worst case

Brute force — time O(n²)

Optimal — time O(n), best and worst case are the same — each pointer moves inward at most n times total

Optimal — space O(1)

Code

// Given an array of heights, height[i] is the height of a vertical
// line at position i. Find two lines that, together with the x-axis,
// form a container holding the most water. Return the max area.
// Area = min(height[left], height[right]) * (right - left).

// --- Brute force: check every pair of lines ---
function maxAreaBrute(heights) {
  let max = 0;
  for (let i = 0; i < heights.length; i++) {
    for (let j = i + 1; j < heights.length; j++) {
      const area = Math.min(heights[i], heights[j]) * (j - i);
      max = Math.max(max, area);
    }
  }
  return max;
}

// --- Optimal: two pointers from both ends, moving inward ---
// Start as wide as possible. The shorter line is always the bottleneck,
// so moving the taller pointer inward can only shrink width without
// ever increasing height — moving the SHORTER one is the only move
// that could possibly find something better.
function maxArea(heights) {
  let left = 0;
  let right = heights.length - 1;
  let max = 0;

  while (left < right) {
    const area = Math.min(heights[left], heights[right]) * (right - left);
    max = Math.max(max, area);

    if (heights[left] < heights[right]) left++;
    else right--;
  }
  return max;
}

// --- Example Usage ---
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
console.log(maxAreaBrute([1, 8, 6, 2, 5, 4, 8, 3, 7])); // 49
console.log(maxArea([1, 1])); // 1