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[i1])
# Fill right_max array
right_max[n1] = heights[n1]
for i in range(n2, 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 histogramlike elevation map. Let’s break down the code for clarity:

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

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.

Initialization:
n = len(heights)
: Determines the length of theheights
list.left_max = [0] * n
: Initializes a list of the same length asheights
to store the maximum height to the left of each bar.right_max = [0] * n
: Similar toleft_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.

Populating the
left_max
Array: The loop
for i in range(1, n)
populatesleft_max
with the maximum height to the left of each bar. left_max[i] = max(heights[i], left_max[i1])
: 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.
 The loop

Populating the
right_max
Array: The loop
for i in range(n2, 1, 1)
fills theright_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.
 The loop

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]
andright_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.
 The final loop

Returning the Total Trapped Water:
return water_trapped
: After completing the loop, the function returns the total amount of trapped water.

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]
.
 An example is provided to demonstrate the use of this function with a specific set of heights
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.