Container With Most Water: Maximizing the Area
The Prompt
You are given an integer array `height` of length `n`. There are `n` vertical lines drawn such that the two endpoints of the `i`-th line are `(i, 0)` and `(i, height[i])`. Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store.
Understanding the Problem
Picture vertical lines on a graph — each line's height comes from the array. You pick any two lines to act as the walls of a container; the x-axis is the floor. Water fills to the shorter wall, so the area is width × min(height[l], height[r]).
What a small but vital insight: the width is largest at the start (the two ends of the array), and it can only shrink as pointers move inward. So every inward move must be justified by the hope of a taller wall.
The Interview Flow
Interviewer
Given an array of heights representing vertical lines, how would you find the maximum amount of water that can be contained between any two lines?
Candidate
The amount of water is determined by the shorter of the two lines (the height) and the distance between them (the width). A brute-force O(n^2) solution would be to calculate the area for every possible pair of lines and keep track of the maximum.
Interviewer
Correct. How can we optimize this to O(n)?
Candidate
I can use a two-pointer approach. I'll start with one pointer at the beginning (`left`) and one at the end (`right`). This gives the maximum possible width.
Interviewer
How do you decide which pointer to move?
Candidate
At each step, I calculate the area formed by the lines at `left` and `right`. The area is `(right - left) * min(height[left], height[right])`. I update my maximum area found so far. Now, to have a chance of finding a larger area, I need to find a taller line. Since my width is decreasing, my only hope is to increase the height. The height is limited by the shorter of the two lines. Therefore, it makes sense to move the pointer of the shorter line inward, hoping to find a taller line that might create a larger area with the other, taller line.
Interviewer
That's a great greedy strategy. Why does that guarantee we don't miss the optimal solution?
Candidate
By moving the shorter line's pointer, we are discarding the current shorter line. We know that any container we could form with this shorter line and any line inside the current window will have a smaller width and a height that is at most the same. So, no better solution can be found using the shorter line. We must seek a taller line.
Interviewer
Excellent reasoning. Please implement it.
Why does two-pointer work here?
Start with both pointers at the ends — maximum width. The only reason to give up width is to find more height, and only the shorter wall limits the area. Moving the taller wall inward can never help: width shrinks and the limiting height stays the same.
So the rule is mechanical: always move the pointer at the shorter wall. Each step eliminates every pair that could have used that discarded wall — which is exactly why one O(n) pass covers all O(n²) pairs.
O(n) Greedy Solution with Two Pointers
- Initialize `maxArea = 0`, a `left` pointer at index 0, and a `right` pointer at the last index.
- Loop as long as `left` is less than `right`.
- Calculate the current width: `width = right - left`.
- Calculate the current height: `h = min(height[left], height[right])`.
- Calculate the current area: `area = width * h`.
- Update `maxArea = max(maxArea, area)`.
- Now, apply the greedy choice: if `height[left] < height[right]`, increment `left`. Otherwise, decrement `right`.
- Continue the loop until the pointers meet.
- Return `maxArea`.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function maxArea(height) {
let maxArea = 0;
let left = 0;
let right = height.length - 1;
while (left < right) {
const h = Math.min(height[left], height[right]);
const w = right - left;
const area = h * w;
maxArea = Math.max(maxArea, area);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}Explanation
Walk the canonical example [1, 8, 6, 2, 5, 4, 8, 3, 7] and watch the pointers converge — the area only needs to be recomputed once per step.
1Widest container first: area = min(1, 7) × 8 = 8. The left wall (height 1) is shorter — it is the limit, so move l.
2l = 1 now: area = min(8, 7) × 7 = 49 — the best we will ever see. The right wall (7) is shorter now, so move r.
3r = 6: area = min(8, 8) × 5 = 40 < 49. Pointers keep converging; no later pair can beat 49 because width only shrinks.
Complexity Analysis
TIME
O(n)
SPACE
O(1)
Finished working through this one?
Mark it complete to track it on your Data Structures path.