Skip to main content

15. Container With Most Water

mediumAsked at Ramp

Find two heights that hold the largest area of water.

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

Problem

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container that holds the most water.

Constraints

  • n == height.length
  • 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

Test every pair of lines.

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

Tradeoff:

2. Two pointers shrink toward the taller side

Start at the ends; always move the shorter pointer inward, since the shorter line bounds the area and moving the taller side could only shrink width without gaining height.

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

Tradeoff:

Ramp-specific tips

Ramp likes this for the bound-tightening argument — the same shape shows up when their approval-graph engine narrows a spend window from both ends to find the tightest matching policy.

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

Practice these live with InterviewChamp.AI →