How to Solve the Trapping Rain Water Problem in Python

Compute the total water trapped between elevation bars using a two-pointer O(n) algorithm.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 17 views 0 copies

algorithms two-pointers arrays rain-water interview

Python code

31 lines
Python 3.9+
Run it 
def trap(height):
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    
    return water

if __name__ == "__main__":
    # Example: elevation map [0,1,0,2,1,0,1,3,2,1,2,1]
    # Expected trapped water: 6
    elevation = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    result = trap(elevation)
    print(f"Elevation: {elevation}")
    print(f"Trapped water: {result} units")

Output

stdout 
Elevation: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
Trapped water: 6 units

How it works

The two-pointer technique keeps track of the maximum height seen from the left and right sides. At each step, we move the pointer on the side with the smaller current height, because the water level there is bounded by the opposite side's maximum. If the current height is less than the current max, we add the difference to the total; otherwise we update the max. This approach avoids extra memory and runs in linear time.

Common mistakes

  • Forgetting to handle an empty input list, causing an IndexError.
  • Using both pointers independently without comparing heights, which can overcount water.
  • Misunderstanding that you need the maximum height on each side to determine the trapped water level.
  • Using a brute-force O(n^2) solution that times out on large arrays.

Variations

  1. Use a stack-based approach to track left boundaries and compute water area when a right boundary is found.
  2. Precompute prefix and suffix maximum arrays to calculate water for each bar in O(n) time and O(n) space.

Real-world use cases

  • Used in coding interviews to assess understanding of optimal array processing algorithms.
  • Can model how much liquid is retained in physical container designs given cross-section profiles.
  • Used in image processing to fill holes or analyze topographic surface water accumulation.

Sponsored

Run this sample

Open the browser IDE to tweak the example and see results without installing anything.

Open editor

More from Algorithms & data structures

Keep learning

Related tutorials and quizzes for this topic.

Tutorials

Quizzes