Rainwater Trapping

December 31, 2023

Problem #

Given an array of integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Solution #

Here’s the Python code for solving the problem of computing how much water can be trapped after raining, given an array of integers representing an elevation map:

def trapRainWater(heights):
    """
    Compute how much water can be trapped after raining in an elevation map.

    Args:
    heights (List[int]): List of integers representing the elevation of each bar in the histogram.

    Returns:
    int: Total amount of trapped rain water.
    """
    if not heights:
        return 0

    n = len(heights)
    left_max = [0] * n
    right_max = [0] * n
    water_trapped = 0

    # Fill left_max array
    left_max[0] = heights[0]
    for i in range(1, n):
        left_max[i] = max(heights[i], left_max[i-1])

    # Fill right_max array
    right_max[n-1] = heights[n-1]
    for i in range(n-2, -1, -1):
        right_max[i] = max(heights[i], right_max[i+1])

    # Calculate trapped water
    for i in range(n):
        water_trapped += min(left_max[i], right_max[i]) - heights[i]

    return water_trapped

# Example usage
heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
total_water_trapped = trapRainWater(heights)

For the example heights [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1], the function computes the total amount of water trapped after raining, which is 6 units.

The code works by first calculating the maximum height to the left and right of each bar. Then, for each bar, it determines how much water can be trapped on top of it, which is the minimum of the maximum heights to its left and right minus its own height. The total trapped water is the sum of the trapped water at each bar.

Soltuion Analysis #

The provided Python code calculates how much water can be trapped after raining in a histogram-like elevation map. Let’s break down the code for clarity:

1. Function Definition:

   • def trapRainWater(heights):
   • This function, trapRainWater, takes one argument heights, which is a list of integers representing the elevation of each bar in the histogram.

2. Edge Case Handling:

   • if not heights: return 0
   • If the heights list is empty, the function returns 0, as no water can be trapped in an empty histogram.

3. Initialization:

   • n = len(heights): Determines the length of the heights list.
   • left_max = [0] * n: Initializes a list of the same length as heights to store the maximum height to the left of each bar.
   • right_max = [0] * n: Similar to left_max, this list will store the maximum height to the right of each bar.
   • water_trapped = 0: A variable to keep track of the total amount of trapped water.

4. Populating the left_max Array:

   • The loop for i in range(1, n) populates left_max with the maximum height to the left of each bar.
   • left_max[i] = max(heights[i], left_max[i-1]): For each bar, the maximum height to its left is either its own height or the maximum height to the left of the previous bar, whichever is greater.

5. Populating the right_max Array:

   • The loop for i in range(n-2, -1, -1) fills the right_max array in a similar manner, but in reverse order (from right to left).
   • right_max[i] = max(heights[i], right_max[i+1]): This stores the maximum height to the right of each bar.

6. Calculating Trapped Water:

   • The final loop for i in range(n) calculates the trapped water above each bar.
   • water_trapped += min(left_max[i], right_max[i]) - heights[i]: The water trapped above each bar is the difference between the smaller of the two heights (left_max[i] and right_max[i]) and the height of the bar itself.
   • This calculation is based on the fact that water trapped above a bar is determined by the shorter of the tallest bars to its left and right.

7. Returning the Total Trapped Water:

   • return water_trapped: After completing the loop, the function returns the total amount of trapped water.

8. Example Usage:

   • An example is provided to demonstrate the use of this function with a specific set of heights [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1].

This code effectively calculates the amount of rainwater that can be trapped between the bars (representing elevations) in a given elevation map, which is a common problem in computational geometry and algorithms.