Container With Most Water

Medium

Problem

height[i] is a vertical line at position i. Choose two lines that, together with the x-axis, hold the most water. The water level is set by the shorter line. Return the maximum amount.

Example 1

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

Lines at indices 1 and 8: min(8, 7) × 7.

Test cases

Case 1

Input:    [1,8,6,2,5,4,8,3,7]
Expected: 49

Case 2

Input:    [1,1]
Expected: 1

Case 3

Input:    [4,3,2,1,4]
Expected: 16

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Every pair

Time O(n²)Space O(1)

Area = width × shorter height, for all pairs.

function maxArea(h) {
let best = 0;
for (let i = 0; i < h.length; i++)
for (let j = i + 1; j < h.length; j++)
best = Math.max(best, (j - i) * Math.min(h[i], h[j]));
return best;
}

2. Two pointers, move the shorter side

Time O(n)Space O(1)

Moving the taller line can only shrink width without raising the limiting height, so always move the shorter one.

function maxArea(h) {
let l = 0, r = h.length - 1, best = 0;
while (l < r) {
best = Math.max(best, (r - l) * Math.min(h[l], h[r]));
h[l] < h[r] ? l++ : r--;
}
return best;
}