March 24
Container With Most Water
How to justify why only the shorter side makes sense to move and use that to shrink the search.
Arrays and Two Pointers Intermediate 18 min TypeScript
Given an array of integers height, where each value represents the height of a vertical line, find two lines that together with the x-axis form a container that stores the most water.
Return the maximum area.
Example:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
What to notice before coding
- Width is the distance between the indexes.
- The usable height of the container is the smaller of the two sides.
- The hard part is not computing area. It is justifying which pointer to move.
Common mistakes
- moving the taller pointer by intuition instead of argument
- forgetting that the container height is capped by the shorter side
Step 1 — Understand the area formula
The area between two lines is:
width * usableHeight
Where:
width = right - leftusableHeight = min(height[left], height[right])
The shorter side is in charge.
Step 2 — Write the correct baseline
The baseline compares every possible pair:
export function maxArea(height: number[]): number {
let best = 0
for (let left = 0; left < height.length; left += 1) {
for (let right = left + 1; right < height.length; right += 1) {
const width = right - left
const currentHeight = Math.min(height[left], height[right])
best = Math.max(best, width * currentHeight)
}
}
return best
}
It works. But it does not use any structure of the problem.
Step 3 — Ask which side is worth moving
If the left side is shorter, then it is limiting the area.
If you move the right side, the width shrinks and the limiting side stays the same.
That cannot improve the best area for that base pair.
So when one side is limiting, only that side is worth replacing.
Step 4 — Use two pointers with justified elimination
Start with the maximum possible width:
leftat the beginningrightat the end
At each step:
- compute the area
- move the pointer at the smaller height
- try to find a better limiting height even with smaller width
The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.
Starter code
export function maxArea(height: number[]): number {
// your solution here
return 0
}
Haven't solved it yet?
Viewing the solution now may reduce learning. It's worth trying a bit more.
Open the reference solution
Without JavaScript, the reference solution is shown inline instead of in a dialog.
Solution
Final complexity
Time: O(n)
Space: O(1)
Solution 1 — Test every pair
Useful as a baseline, but too expensive.
export function maxArea(height: number[]): number {
let best = 0
for (let left = 0; left < height.length; left += 1) {
for (let right = left + 1; right < height.length; right += 1) {
const width = right - left
const currentHeight = Math.min(height[left], height[right])
best = Math.max(best, width * currentHeight)
}
}
return best
}Solution 2 — Two pointers with greedy reasoning
Now the search only moves where a real improvement is still possible.
export function maxArea(height: number[]): number {
let left = 0
let right = height.length - 1
let best = 0
while (left < right) {
const width = right - left
const currentHeight = Math.min(height[left], height[right])
best = Math.max(best, width * currentHeight)
if (height[left] <= height[right]) {
left += 1
} else {
right -= 1
}
}
return best
}The value here is not only getting the answer. It is being able to justify the move.
What to say in the interview
A strong short explanation would be:
The area depends on width and the shorter side. I start with the widest possible container and, at each step, move the pointer at the shorter side. The reason is that moving the taller side does not fix the current bottleneck and still reduces width. So only the limiting side can open a chance for improvement.
That shows that you:
- understood what really limits the area
- justified the greedy choice
- turned the algorithm into an argument, not a template
When this pattern shows up again
The same pattern comes back when you need to:
- compare extremes
- move only the side limiting the current answer
- eliminate search with an impossibility argument
- explain why a greedy choice makes sense
The point is not memorizing “move the smaller one.”
The point is justifying why moving the larger one does not help.