4
\$\begingroup\$

This is from Leetcode

Trapping Rain Water

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
\$\endgroup\$
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – kushj Aug 5 '19 at 17:36
4
\$\begingroup\$

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
    return total_area + plateau_height * plateau_width - sum(landscape)

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.