Pick two walls that hold the most water. Start at both ends and always move the shorter wall inward, since it caps the area.
▼The problem
LeetCode 11 (Medium). Given the heights of n vertical lines, pick two that, with the x-axis, hold the most water. The water rises only to the shorter line, so the area is min(h[i], h[j]) × (j − i). Return the largest area.
Example: [1, 8, 6, 2, 5, 4, 8, 3, 7] → 49 (the 8 at index 1 and the 7 at index 8: 7 high, 7 apart).
The solution
def maxArea(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
area = min(height[left], height[right]) * (right - left)
best = max(best, area)
if height[left] < height[right]:
left += 1
else:
right -= 1
return bestTranscript
Container With Most Water. You get a row of lines with different heights. Any two of them hold water between them, up to the shorter line. So the area is the shorter height times the distance between them. Find the biggest area.
Take one, eight, six, two, five, four, eight, three, seven. The best pair is the eight near the start and the seven at the end: seven high and seven apart, so forty-nine.
The simple way tries every pair. Nine lines make thirty-six pairs, and n lines make about n squared over two. That's order n squared.
Better: start with the two outer lines, the widest container. Every step inward makes it narrower. Moving the taller line can't help: the water is still capped by the shorter one. So always move the shorter line in, hoping for a taller one.
In code: a left pointer and a right pointer. While they haven't met, compute the area and keep the best. Then step the shorter side inward. On a tie, either one works.
Let's run it. One and seven, eight apart: area eight. The left is shorter, so it moves. Eight and seven, seven apart: forty-nine, the new best. Now the right is shorter. Three gives eighteen. Eight and eight tie at forty, and the right moves. The rest stay smaller: sixteen, fifteen, four, six. The pointers meet. The answer is forty-nine.
Each step moves one pointer, so it's one pass: linear time. And just a few variables: constant space.
Start wide, move the shorter line, keep the best. That's Container With Most Water.