AI Hints
Home›DSA in Python Tutorial›Interview Method
DSA in Python · Lesson 104 of 132

Practice: Most Water

Two pointers again.

⏱ 2 min read▶ Video at 2:04:29🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Practice: Most Water
From the video: Practice: Most Water
  • 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.

water.pypython
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]))
Output
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.

keyvalue
Brute forceO(n²)
Insightthe short wall limits
Movethe shorter one
ResultO(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)
Next up: Practice: Three Sum — sort, then two pointers