Medium Greedy Shrink Two Pointers
In plain English: Pick two vertical lines to form a container. Find the pair that holds the most water.
Start with the widest container (both ends). The shorter line is the bottleneck — moving the taller one inward can only reduce width without increasing height. So always move the shorter pointer inward.
Prompt
Given n non-negative integers representing heights of vertical lines, find two lines that together with the x-axis form a container that holds the most water.
Try to write it from scratch before scrolling down.
Solution
def max_area(height):
l, r = 0, len(height) - 1
best = 0
while l < r:
w = r - l
h = min(height[l], height[r])
best = max(best, w * h)
if height[l] < height[r]:
l += 1 # move shorter line inward
else:
r -= 1
return best
# Test: max_area([1,8,6,2,5,4,8,3,7]) == 49 (lines at indices 1,8)