Skip to main content

13. Container With Most Water

mediumAsked at ByteDance

Pick two lines that hold the most water — ByteDance uses it to validate two-pointer reasoning before progressing to ranking-score gap problems.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given heights where height[i] is the height of a vertical line at x = i, find two lines that with the x-axis form a container holding the most water. Return that maximum area.

Constraints

  • 2 <= n <= 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. Brute force

Compute the area for every pair (i, j).

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

Tradeoff:

2. Two pointers

Start at both ends and always move the shorter side inward. The shorter line caps the area, so moving the taller side cannot improve it.

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

Tradeoff:

ByteDance-specific tips

ByteDance interviewers expect a one-line proof of why moving the shorter pointer is safe, exactly the kind of invariant their ranking engineers write down before any optimization.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

More ByteDance coding interview questions

See all ByteDance problems →

Companies that also ask Container With Most Water