AI Hints
Home›DSA in Python Tutorial›Array Interview Problems
DSA in Python · Lesson 108 of 132

Practice: Trapping Rain Water

Water between the walls.

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

After rain, water collects between walls of different heights. How much water is trapped in total? This is a famous hard problem. Pause, and think about one single position. How high can water rise there?

Practice: Trapping Rain Water
From the video: Practice: Trapping Rain Water
  • Water collects between walls
  • How much in total?
  • Think about one position

Two pointers, tracking the tallest

Water above a position rises to the shorter of the tallest wall on its left, and the tallest wall on its right. With two pointers, we move in from whichever side has the shorter tallest wall, because that side decides the water level. Each step adds the water above that position. Run it. Six units of water are trapped.

rain.pypython
def trap(heights):
    left, right = 0, len(heights) - 1
    left_max = right_max = water = 0
    while left < right:
        if heights[left] < heights[right]:
            left_max = max(left_max, heights[left])
            water += left_max - heights[left]
            left += 1
        else:
            right_max = max(right_max, heights[right])
            water += right_max - heights[right]
            right -= 1
    return water

print(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
Output
6

Hard problems, simple pieces

Hard problems are usually simple ideas combined. Here, it's two pointers, plus tracking a maximum. Start by asking what decides the answer at one position. Then find a way to know that quickly for every position. That question cracks many hard problems.

keyvalue
At one spotmin(tallest left, tallest right)
Two pointersmove the smaller side
Addlevel − height
CostO(n), O(1) space

Summary

Water at each spot depends on the shorter of the tallest walls on each side. Two pointers solve it in O of N. Next, interview problems about trees and lists.

Key takeaways
  • Tallest on each side
  • Move the smaller side
  • O(n)
Next up: Practice: Invert a Binary Tree — a mirror image