Practice: Most Water
Two pointers again.
Here's a row of walls with different heights. Pick two walls, and the water they can hold is the distance between them, times the height of the shorter wall. Which pair holds the most water? Pause, and try the method. Brute force first.

- Walls of different heights
- Width times the shorter wall
- Which pair holds most?
Move the shorter wall
The brute force checks every pair, O of N squared. The better way starts with the widest pair, one wall at each end. The area is limited by the shorter wall, so moving the taller one can never help. So we always move the shorter wall inwards, hoping to find a taller one. Run it. Forty nine, found in one pass.
def most_water(heights):
left, right, best = 0, len(heights) - 1, 0
while left < right:
width = right - left
best = max(best, width * min(heights[left], heights[right]))
if heights[left] < heights[right]:
left += 1
else:
right -= 1
return best
print(most_water([1, 8, 6, 2, 5, 4, 8, 3, 7]))49
What the interviewer hears
A good answer here sounds like this. The brute force is O of N squared. I can do better with two pointers, starting wide. The shorter wall limits the area, so it's the one to move. That's O of N time, and O of one space. You've explained why it works, not just what it does.
| key | value |
|---|---|
| Brute force | O(n²) |
| Insight | the short wall limits |
| Move | the shorter one |
| Result | O(n) time, O(1) space |
Summary
Start wide, and always move the shorter wall. Two pointers solve it in O of N. Next, finding three numbers that add to zero.
Key takeaways- Start at both ends
- Move the shorter wall
- O(n)