Skip to main content

34. Container With Most Water

mediumAsked at Ola

Find two lines that together with the x-axis form a container holding the most 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, and return the maximum amount of water it can store.

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 pairs

Try every pair of lines and compute area.

Time
O(n^2)
Space
O(1)
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

Start at the ends; always move the shorter side inward since moving the taller can only decrease the area.

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

Tradeoff:

Ola-specific tips

Ola checks if you can argue why the two-pointer greedy never misses the optimum; tie it to picking the best fare-window between two surge multipliers.

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

Practice these live with InterviewChamp.AI →