How do you solve Container With Most Water, and why is moving the shorter wall the right move?
You start with a pointer at each end, work out the area, and move the shorter wall inwards.
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
area = (right - left) * min(height[left], height[right])
if area > best:
best = area
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
So why is moving the shorter wall the right move? Because the area is limited by the shorter wall. The area is the width times the shorter of the two heights, so no matter how wide it is, the shorter wall is what decides the answer.
So if you move the taller wall inwards, the width gets smaller and the limiting height stays the same, because the shorter wall has not moved. So the area can only get smaller. That move is wasted.
Moving the shorter wall inwards is the only move that can help, because it is the only one that can raise the limiting height. The width gets smaller, but you have a chance of finding a taller wall, and a tall enough wall makes up for the lost width.
So the rule to remember is this. When a step can only make one of the two things worse, move the thing that is limiting the answer.
The next two questions in this topic return the walls themselves and compare with the slow version.