Container With Most Water
Asked at Google, Meta, Amazon, Microsoft, Oracle, Salesforce, Walmart
Problem
Given an array of heights, find two lines that together with the x-axis form a container that holds the most water. This problem tests your ability to use two pointers and reason about why a greedy approach works.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all Google questions → | |
| Meta | Medium | View all Meta questions → |
| Amazon | Medium | View all Amazon questions → |
| Microsoft | Medium | View all Microsoft questions → |
| Oracle | Medium | View all Oracle questions → |
| Salesforce | Medium | View all Salesforce questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Brute force: try every pair of lines. For each pair (i, j), area = min(height[i], height[j]) × (j - i). That's O(n²). Two pointers bring it to O(n).
Start with the widest container: left pointer at index 0, right pointer at index n-1. The area is limited by the shorter line. Width is maximized.
Key insight: to find a larger area, you need either a taller line OR a wider container. Since width only decreases as you move pointers inward, you need a taller line to compensate. So always move the shorter pointer — the taller one might give you a bigger area.
Why moving the taller pointer is wasteful: if you move the taller pointer, the new width is smaller, and the height is still limited by the shorter line. You can never improve. But if you move the shorter pointer, you might find a taller line that compensates for the lost width.
Visual walkthrough for [1,8,6,2,5,4,8,3,7]:
0 1 2 3 4 5 6 7 8
1 8 6 2 5 4 8 3 7
left=0, right=8. min(1,7)×8 = 8. Move left (1 < 7).
left=1, right=8. min(8,7)×7 = 49. Move right (7 < 8).
left=1, right=7. min(8,3)×6 = 18. Move right (3 < 8).
left=1, right=6. min(8,8)×5 = 40. Move right (equal, either works).
left=1, right=5. min(8,4)×4 = 16. Move right (4 < 8).
left=1, right=4. min(8,5)×3 = 15. Move right (5 < 8).
left=1, right=3. min(8,2)×2 = 4. Move right (2 < 8).
left=1, right=2. min(8,6)×1 = 6. Move right (6 < 8).
Pointers meet. Best = 49.
Optimal Approach
Place left pointer at 0, right pointer at n-1. Calculate area = min(height[left], height[right]) × (right - left). Update max area. Move the pointer at the shorter line inward.
The invariant: at each step, all pairs involving the shorter line and any line between the pointers have been considered (or are guaranteed to be smaller). Moving the shorter line is safe.
Time: O(n) — each pointer moves at most n times. Space: O(1).
What Trips People Up in Real Interviews
Trying to use brute force (check all pairs). That's O(n²) and will time out. The two-pointer approach is O(n) and is what the interviewer expects.
Moving the pointer with the larger height. That's wrong — you should move the pointer with the smaller height. Moving the larger one can only decrease the area (shorter width, height can't increase beyond the smaller).
Forgetting that the area is min(height[left], height[right]) × (right - left). The height is limited by the shorter wall, not the taller one.
Not initializing the result to 0. If no container has positive area (all heights are 0), return 0.
Initializing the result to -1 instead of 0. Area is always non-negative since heights are non-negative, so the minimum possible answer is 0, not -1.
Solution Code
def maxArea(height):
lo, hi = 0, len(height) - 1
best = 0
while lo < hi:
area = min(height[lo], height[hi]) * (hi - lo)
best = max(best, area)
if height[lo] < height[hi]:
lo += 1
else:
hi -= 1
return bestFrequently Asked Questions
What is the Container With Most Water problem?
Given an array of heights, find two lines that together with the x-axis form a container that holds the most water. This problem tests your ability to use two pointers and reason about why a greedy approach works.
How do you solve Container With Most Water?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Container With Most Water?
Container With Most Water is asked at Google, Meta, Amazon, Microsoft, Oracle, Salesforce, Walmart. It is a medium difficulty problem.
What are common mistakes on Container With Most Water?
- Trying to use brute force (check all pairs). That's `O(n²)` and will time out. The two-pointer approach is `O(n)` and is what the interviewer expects.
- Moving the pointer with the larger height. That's wrong — you should move the pointer with the smaller height. Moving the larger one can only decrease the area (shorter width, height can't increase beyond the smaller).
- Forgetting that the area is min(`height[left]`, `height[right]`) × (right - left). The height is limited by the shorter wall, not the taller one.
- Not initializing the result to 0. If no container has positive area (all heights are 0), return 0.
- Initializing the result to -1 instead of 0. Area is always non-negative since heights are non-negative, so the minimum possible answer is 0, not -1.