Given an array of heights representing vertical lines, find two lines that, together with the x-axis, hold the most water, and return that maximum area.
Video coming soon
We're producing a video walkthrough — check back soon.
Given an array of heights representing vertical lines, find two lines that, together with the x-axis, hold the most water, and return that maximum area.
The problem that makes converging two pointers click as a greedy elimination argument rather than a brute-force shortcut — every pointer move must be provably safe to discard the option it leaves behind.
Whenever the answer is defined by a width between two chosen positions times a value bounded by the smaller of the two, and you're tempted to check every pair, look for a greedy argument that lets converging pointers discard one whole side at a time.
Start two pointers at the outermost lines — this is the widest container possible. At each step, compute the area as min(height[left], height[right]) * (right - left) and track the best seen so far. The key insight is which pointer to move: the container's height is capped by the shorter line, so keeping the taller line and moving it inward can only reduce the width while the height cap stays the same or gets worse — it can never produce a better answer. Moving the shorter line, however, might reveal a taller line that raises the height cap, even though the width shrinks. So always move the pointer at the shorter line inward, and stop once the pointers meet.
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int best = 0;
while (left < right) {
int h = Math.min(height[left], height[right]);
best = Math.max(best, h * (right - left));
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return best;
}
}