11. Container With Most Water
Asked at Google, Meta, Amazon, Microsoft and 6 more
Difficulty
Medium
Time
O(n)
Space
O(1)
Pattern
Array
Companies
10
Problem
You are given an array height. Think of each value as the height of a vertical wall standing at that index. The bottom of every wall sits on the x-axis, so wall i runs from point (i, 0) up to (i, height[i]).
Pick any two walls. Together with the x-axis they form a container. The water it can hold is min(height[i], height[j]) * (j - i): the shorter wall decides how high the water can rise, and the distance between the walls is the width. The container must stay upright — you may not tilt it.
Return the largest amount of water any pair of walls can hold.
Two walls plus the x-axis make a container
Constraints
- ●
2 <= height.length <= 10^5 - ●
0 <= height[i] <= 10^4
Examples
height = [1,8,6,2,5,4,8,3,7]49height = [1,1]1Asked At
10 companies| 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 → |
| Bloomberg | Medium | View all Bloomberg questions → |
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
| Flipkart | Medium | View all Flipkart 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.
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).
Two pointers, move the shorter wall
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
O(n) timedef 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 runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Container With Most Water?
Container With Most Water is asked at Google, Meta, Amazon, Microsoft, Oracle, Salesforce, Walmart, Bloomberg, Goldman Sachs, Flipkart. 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.