14. Container With Most Water
height[i] is the height of a vertical line at position i. Pick two lines that, together with the x-axis, hold the most water. Return that amount: min(height[i], height[j]) × (j − i).
Example 1
Input:
height = [2,5,1,4,3]Output:
9Explanation: Lines at positions 1 (height 5) and 4 (height 3): min(5, 3) × 3 = 9.
Example 2
Input:
height = [4,3,2,1,4]Output:
16Hint 1
Start with the widest container.
Hint 2
Moving the taller line can never help: the width shrinks and the height is still capped by the shorter line.
Approach 1: All pairs
Try every pair of lines.
⏱ Time O(n²)💾 Space O(1)
Approach 2: Two pointers ✅
Start wide; always move the shorter side inward.
⏱ Time O(n)💾 Space O(1)
Reference solution for Two pointers (time O(n), space O(1)). Each solution passes every test in all four languages.
class Solution:
def maxArea(self, height: List[int]) -> int:
lo, hi, best = 0, len(height) - 1, 0
while lo < hi:
best = max(best, min(height[lo], height[hi]) * (hi - lo))
if height[lo] < height[hi]: # the shorter line limits the area: move it
lo += 1
else:
hi -= 1
return bestclass Solution {
public int maxArea(int[] height) {
int lo = 0, hi = height.length - 1, best = 0;
while (lo < hi) {
best = Math.max(best, Math.min(height[lo], height[hi]) * (hi - lo));
if (height[lo] < height[hi]) lo++; else hi--; // move the shorter line
}
return best;
}
}class Solution {
public:
int maxArea(vector<int>& height) {
int lo = 0, hi = (int)height.size() - 1, best = 0;
while (lo < hi) {
best = max(best, min(height[lo], height[hi]) * (hi - lo));
if (height[lo] < height[hi]) lo++; else hi--; // move the shorter line
}
return best;
}
};function maxArea(height) {
let lo = 0, hi = height.length - 1, best = 0;
while (lo < hi) {
best = Math.max(best, Math.min(height[lo], height[hi]) * (hi - lo));
if (height[lo] < height[hi]) lo++; else hi--; // move the shorter line
}
return best;
}Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.
This problem is explained in the lesson Two Pointers.
Run your code to see results here.