Python – Solve the Trapping Rain Water Problem Using an Array

The trapping rain water problem is a popular question in data structures and algorithms (DSA) interviews. In this problem, you are given an array where each element represents the elevation at that point. The task is to determine how much water can be trapped between the elevations after it rains.

Problem Statement

Given an array height of non-negative integers representing an elevation map (where the width of each bar is 1), calculate the total amount of rainwater that can be trapped after raining.

Sample Input and Output

Example 1:

</>
Copy
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Example 2:

</>
Copy
Input: height = [4,2,0,3,2,5]
Output: 9

Solution Approach

The idea behind the solution is to determine the maximum height to the left and right of each index and use these values to calculate the water that can be trapped at that position. Follow these steps:

  1. Create two arrays: left_max and right_max to store the highest bar from the left and right at each index.
  2. Populate left_max: Iterate from left to right, storing the maximum height encountered so far.
  3. Populate right_max: Iterate from right to left, storing the maximum height encountered so far.
  4. Calculate water at each index: For each index i, the water trapped is the minimum of left_max[i] and right_max[i] minus the current height height[i].
  5. Sum up: Add the water trapped at each index to get the total amount of trapped water.

This approach uses extra space for two auxiliary arrays but efficiently computes the solution in O(n) time.

Python Program

</>
Copy
def trap(height):
    # Return 0 if the input list is empty
    if not height:
        return 0

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

    # Fill left_max array: maximum height to the left of each index
    left_max[0] = height[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])

    # Fill right_max array: maximum height to the right of each index
    right_max[n - 1] = height[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    # Calculate the total trapped water
    water = 0
    for i in range(n):
        # Water trapped at index i is the min of left_max and right_max minus the height at i
        water += min(left_max[i], right_max[i]) - height[i]
        
    return water

# Sample Inputs
height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
height2 = [4,2,0,3,2,5]

# Print outputs
print("Total trapped water for height1:", trap(height1))  # Expected output: 6
print("Total trapped water for height2:", trap(height2))  # Expected output: 9

Conclusion

This tutorial demonstrated how to solve the trapping rain water problem using an array. We outlined the problem statement, provided sample inputs and outputs, and discussed a step-by-step solution approach using auxiliary arrays. The provided Python program implements the solution in an efficient manner. Understanding this problem will help you build a strong foundation in array manipulation and dynamic programming concepts for DSA interviews.