5 Best Ways to Calculate How Much Rainwater Can Be Trapped in Python

Rate this post
Calculating Rainwater Trapping in Python

πŸ’‘ Problem Formulation: Imagine a landscape of varying bar heights, where each bar’s height represents an elevation on a topographic map. The question is how much rainwater could be trapped within the concavities between these elevations after a rainstorm. For a given array of integers representing elevation heights, the output should be a single integer representing the total amount of trapped rainwater.

Method 1: Brute Force Approach

This method involves iterating over each element in the height map and, for each element, finding the highest bar to its left and right. The trapped water over this bar is the minimum of these two highest bars minus the height of the current bar. This method is intuitive but inefficient, with a time complexity of O(n^2).

Here’s an example:

def trap_rain_water(height_map):
    water_trapped = 0
    for i in range(1, len(height_map) - 1):
        left_max = max(height_map[:i])
        right_max = max(height_map[i+1:])
        water_trapped += max(0, min(left_max, right_max) - height_map[i])
    return water_trapped

print(trap_rain_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

Output: 6

This code snippet calculates the amount of trapped rainwater by iterating through each elevation and considering the maximum elevation to its left and right. It is straightforward but performs poorly for large datasets due to its quadratic time complexity.

Method 2: Dynamic Programming Approach

This approach improves upon the brute force method by storing the left and right maxima for each bar in two separate arrays. While it still traverses the height map twice, this method only does so to populate the arrays, enabling a much faster calculation of trapped water with a linear O(n) time complexity.

Here’s an example:

def trap_rain_water(height_map):
    if not height_map:
        return 0

    n = len(height_map)
    left_max = [0] * n
    right_max = [0] * n

    left_max[0] = height_map[0]
    for i in range(1, n):
        left_max[i] = max(height_map[i], left_max[i-1])

    right_max[n-1] = height_map[n-1]
    for i in reversed(range(n-1)):
        right_max[i] = max(height_map[i], right_max[i+1])
        
    water_trapped = 0
    for i in range(n):
        water_trapped += min(left_max[i], right_max[i]) - height_map[i]

    return water_trapped

print(trap_rain_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

Output: 6

The provided code calculates the amount of trapped rainwater by precomputing the highest bars to the left and right of each bar, then iteratively calculating the water level above each bar. This efficient method scales well with large input sizes.

Method 3: Using Stacks

The stack-based solution simulates a real-life scenario where barriers are stacked up and whenever a lower elevation is encountered, it is added to the stack. If a higher elevation is encountered, we pop elements from the stack, calculate the trapped water within the bounded region, and then push the current elevation. The complexity is O(n), making it efficient for large datasets.

Here’s an example:

def trap_rain_water(height_map):
    stack, water_trapped = [], 0
    for i, height in enumerate(height_map):
        while stack and height_map[stack[-1]] < height:
            top = stack.pop()
            if not stack:
                break
            distance = i - stack[-1] - 1
            bounded_height = min(height_map[stack[-1]], height) - height_map[top]
            water_trapped += distance * bounded_height
        stack.append(i)
    return water_trapped

print(trap_rain_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

Output: 6

This code utilizes a stack to store and process the bars’ heights as they appear. When a taller bar is encountered, trapped water is computed based on the height difference and the width between the current bar and the bar at the top of the stack. This method is efficient for one-pass solutions with low memory overhead.

Method 4: Two Pointers Technique

Two pointers approach uses left and right pointers moving towards each other. At each step, the pointer with the lower elevation moves one step towards the other, with the amount of water trapped at each step being determined by the difference in height between the elevation and the current maximum elevation encountered by that pointer. This method uses constant space, performing at O(n) time complexity.

Here’s an example:

def trap_rain_water(height_map):
    left, right = 0, len(height_map) - 1
    left_max, right_max, water_trapped = 0, 0, 0
    while left < right:
        if height_map[left] = left_max:
                left_max = height_map[left]
            else:
                water_trapped += left_max - height_map[left]
            left += 1
        else:
            if height_map[right] >= right_max:
                right_max = height_map[right]
            else:
                water_trapped += right_max - height_map[right]
            right -= 1
    return water_trapped

print(trap_rain_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

Output: 6

The two pointers technique implemented here efficiently computes the trapped rainwater by maintaining two moving pointers that converge in the middle. This algorithm is highly efficient with constant space utilization and fast execution time, making it ideal for time-critical and memory-constrained applications.

Bonus One-Liner Method 5: Intuitive Pythonic Reduction

This one-liner approach leverages Python’s list comprehensions and built-in functions for a concise and elegant solution. It’s a reduction of the dynamic programming approach into a single expression that calculates the trapped rainwater by applying a function across the elevation map. However, its compact nature may sacrifice readability for brevity.

Here’s an example:

trap_rain_water = lambda height_map: sum(
    max(0, min(max(height_map[:i+1]), max(height_map[i:])) - h)
    for i, h in enumerate(height_map)
)

print(trap_rain_water([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

Output: 6

The one-liner provided uses a lambda function to express the calculation in a condensed form. It iterates through the elevation map and summing the differences between each elevation and the maximal waters that can surround it, thus yielding the amount of water that could be trapped at that point.

Summary/Discussion

  • Method 1: Brute Force. Simple but inefficient for large data sets due to its quadratic complexity.
  • Method 2: Dynamic Programming. Optimized with linear complexity and suitable for large data sets, but requires additional space for storing the left and right maxima.
  • Method 3: Using Stacks. Efficient for one-pass solutions, doesn’t need precomputation, and works well for large data sets. It may be complex for beginners to understand.
  • Method 4: Two Pointers Technique. Highly efficient with constant space and linear time complexity. It combines the best aspects of efficiency and simplicity.
  • Method 5: Pythonic Reduction. Extremely concise and elegant, but readability may be poor, and performance is worse than the optimized methods.