Skip to main content

15. Container With Most Water

mediumAsked at Squarespace

Find the pair of vertical lines that hold the most water; Squarespace uses it to test whether you reach for the two-pointer optimization instead of brute force.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given n non-negative integers height[i] representing vertical line heights at position i, find two lines that together with the x-axis form a container that holds the most water. Return the maximum area.

Constraints

  • 2 <= height.length <= 10^5
  • 0 <= height[i] <= 10^4

Examples

Example 1

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

Example 2

Input
height=[1,1]
Output
1

Approaches

1. All pairs

Compute area for every pair of lines and keep the max.

Time
O(n^2)
Space
O(1)
let best=0;
for(let i=0;i<n;i++) for(let j=i+1;j<n;j++)
  best=Math.max(best,(j-i)*Math.min(height[i],height[j]));
return best;

Tradeoff:

2. Two pointers shrinking inward

Start at both ends and always move the shorter side inward, because that's the only way the area can grow.

Time
O(n)
Space
O(1)
function maxArea(height) {
  let l = 0, r = height.length - 1, best = 0;
  while (l < r) {
    const h = Math.min(height[l], height[r]);
    best = Math.max(best, h * (r - l));
    if (height[l] < height[r]) l++; else r--;
  }
  return best;
}

Tradeoff:

Squarespace-specific tips

Squarespace likes a short note that this two-pointer shrink is the same logic their gallery section uses to pick the widest available media slot.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Container With Most Water and other Squarespace interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →