# Trapping Rain Water in Python

This is from Leetcode

My solution is based on Python 3. It was faster than 90% of solutions on Leetcode, but used too much memory. Please what makes this memory hungry? How can I make this more efficient?

def trap(height, bound=None):
storage = 0
temp_storage = 0
left_bound = None
max_left_bound = 0

for elevation in height:
if bound and elevation == bound:
storage += temp_storage
return storage

max_left_bound = max(elevation, max_left_bound)

if not left_bound:
left_bound = elevation
continue

block_capacity = left_bound - elevation
if block_capacity > 0:
temp_storage += block_capacity
continue
storage += temp_storage
temp_storage, left_bound = 0, elevation

if not temp_storage:
return storage

height.reverse()

r_capacity = trap(height, max_left_bound)

storage += r_capacity

return storage

• Without going into code details, I can see that this uses recursion. Python does not really optimize recursion A good guess would be to maybe try converting this in iterative format? – kushj Aug 5 '19 at 17:36

I'm not sure what you mean by "used too much memory" — if I try submitting a copy of your code now, then LeetCode says:

Memory Usage: 12.3 MB, less than 57.53% of Python online submissions for Trapping Rain Water.

It is impossible to know whether the 12.3 MB is a lot or a little without knowing what this includes and how big the test cases were, neither of which LeetCode tells us.

### 1. Review

1. I found it difficult to follow the algorithm because of the proliferation of similarly named variables. There are four variables that contain heights: elevation, bound, left_bound and max_left_bound. How do these variables relate to each other? Is left_bound actually a right bound when iterating over heights in reverse? There are three variables that contain amounts of water: storage, temp_storage and block_capacity. Again, how do these relate to each other?

Finding good names for variables and writing comments to clarify any remaining difficulties, is crucial in writing code that will be maintainable when you come back to it after having forgotten how it works.

2. The trap function modifies the list heights (by reversing it). It's best if functions don't modify their arguments (unless modifying the arguments is the point). Otherwise callers will be surprised by the side-effects. In this case you could easily use reversed(heights) instead of heights.reverse().

3. The code considers each vertical slice through the landscape in turn, adding left_bound - elevation (that is, the current water height minus the current land height) to the total trapped water. But in practice left_bound (the current water height) stays the same for several iterations of the loop, so we could wait until it changes and then add the block of water all at once. See §2 below for how to do this.

### 2. Alternative solution

Consider a typical landscape filled with water:

If we ignore the difference between water and land, and just look at the overall surface level, it should be clear that the filled landscape is made up of rectangles arranged like this:

There is a central "plateau" whose height is the maximum height of the landscape, flanked by staircases that start low at the outside and rise up to the plateau.

If we find the height of the plateau, which is just max(landscape), then we can work inwards from the left and right ends, finding the rectangles in the rising staircases until we reach the plateau height. By summing the rectangles we get the overall area of the filled landscape, and by subtracting the land part, which is just sum(landscape), we get the water part.

def trap2(landscape):
"""Return area of water trapped by landscape (a list of heights)."""
if not landscape:
return 0
plateau_height = max(landscape)
plateau_width = len(landscape)
total_area = 0
for heights in (landscape, reversed(landscape)):
height_max = i_max = 0  # maximum height so far and its index
for i, height in enumerate(heights):
if height > height_max:
total_area += (i - i_max) * height_max
if height == plateau_height:
plateau_width -= i
break
height_max = height
i_max = i


It is a bit clearer, I hope, how this works, and it is several times faster than the code in the post. The reasons why this is faster are (i) the accumulation total_area += ... is done once per rectangle, not once per vertical slice; and (ii) the subtraction of the land part is done once by calling the built-in function sum, which runs in fast compiled code.

The exact speedup depends on the shape of the landscape, but here's a test case where the revised code was about 8 times faster:

>>> from random import choices
>>> from timeit import timeit
>>> HEIGHTS = choices(range(100), weights=(100,) + (1,) * 99, k=1000000)
>>> timeit(lambda:trap(HEIGHTS), number=1) # code in the post
0.31537632799881976
>>> timeit(lambda:trap2(HEIGHTS), number=1) # revised code
0.04002986599880387


But on LeetCode it runs in much the same time as the code in the post — clearly they are not try big enough test cases to detect the difference.