Given an array of heights, find two lines that together with the x-axis form a container that holds the most water.
Place one pointer at the far left and one at the far right, track the best area seen so far, then always move the pointer sitting at the shorter height inward. Moving the taller side inward could only reduce width without any chance of gaining height, so it's never optimal — this greedy squeeze finds the answer in O(n).
How to think about it
What the interviewer is really testing is whether you can justify a greedy move, not just code two pointers. Anyone can place a pointer at each end; the question is whether you can explain why moving the shorter wall — and never the taller one — provably loses nothing. Get that argument out loud and the O(n) solution is yours.
Start by noticing the area between two lines is min(height[left], height[right]) * (right - left). Two forces pull against each other: as the pointers converge, width shrinks, but the height ceiling can rise. That tension, plus the fact that there are exactly two endpoints, is the two-pointer cue. Begin with the widest container — left = 0, right = n - 1 — and record its area. To beat it you need a taller minimum wall, and the only lever you have is moving a pointer. Move the taller one and width falls while the shorter side still caps the height, so the area can only stay equal or drop — never a win. So you always advance the shorter side; it is the only pointer with any chance of meeting a taller wall.
A worked example
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right]) # shorter wall caps the water
w = right - left
best = max(best, h * w)
if height[left] <= height[right]:
left += 1 # always move the shorter side
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # the canonical case
print(max_area([1, 1])) # edge: just two lines
print(max_area([4, 3, 2, 1, 4]))49
1
16The first array peaks at 49. The squeeze opens at left=0 (h=1), right=8 (h=7) for an area of 1*8 = 8, then moves the short left wall in to h=8, which against the 7 on the right gives min(8,7)*7 = 49 — the answer — after which no narrower window can match it. The [1, 1] case is the lower boundary: two unit walls one apart hold 1. And [4, 3, 2, 1, 4] returns 16, the two outer 4s spanning the full width of four, showing the best container is often the widest pair of tall-enough walls rather than the single tallest wall.