Container With Most Water
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
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;}