Skip to main content

10. Container With Most Water

mediumAsked at Autodesk

Pick two lines from a histogram that together with the x-axis contain the largest area of water.

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

Problem

Given n non-negative integers height[0..n-1] representing vertical lines on the x-axis, find two lines that together with the x-axis form a container that holds the most water. Return the maximum water 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 (i,j) and keep the maximum.

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, Math.min(h[i],h[j])*(j-i));

Tradeoff:

2. Two-pointer shrink

Start at the widest pair and move whichever side is shorter inward, since width can only decrease. Linear sweep.

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

Tradeoff:

Autodesk-specific tips

Autodesk values geometric intuition like this because the same two-pointer shrink idea drives sweep-line containment tests in 2D drafting.

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 Autodesk interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →