Trapping Rain Water - Python Solution

1. Introduction

The "Trapping Rain Water" problem is a well-known algorithmic challenge that involves calculating the amount of water that can be trapped between bars in an elevation map. This problem is a classic example of using dynamic programming and two-pointer techniques to solve complex problems efficiently.

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, the task is to compute how much water it can trap after raining. The integers represent the height of the bars, and the water can be trapped between them.

2. Solution Steps

1. Create two arrays, left_max and right_max, to store the maximum height to the left and right of each bar.

2. Initialize left_max with the first element of the input array and right_max with the last element.

3. Fill left_max and right_max by iterating over the input array from left to right and right to left, respectively.

4. Calculate the amount of water that can be trapped on top of each bar as the minimum of left_max and right_max at that position minus the height of the bar.

5. Sum up the water trapped on all bars to get the total amount of trapped water.

6. Return the total trapped water.

3. Code Program

def trap(height):
    if not height:
        return 0

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

    for i in range(1, n):
        left_max[i] = max(left_max[i - 1], height[i])
    for i in range(n - 2, -1, -1):
        right_max[i] = max(right_max[i + 1], height[i])

    trapped_water = 0
    for i in range(n):
        trapped_water += min(left_max[i], right_max[i]) - height[i]

    return trapped_water

# Example Usage
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # Output: 6

Output:

6

Explanation:

1. Left and Right Maximum Heights: left_max and right_max arrays store the highest bar on the left and right of each bar, respectively.

2. Array Initialization: The arrays are initialized based on the first and last elements of the input.

3. Filling Arrays: The arrays are filled by iterating over the elevation map.

4. Water Calculation: The water trapped above each bar is calculated as the minimum of left_max and right_max minus the height of the bar.

5. Total Water Trapped: The total amount of water trapped is calculated by summing up the water on top of each bar.

6. Efficient Solution: The solution uses O(n) time and space complexity, efficiently solving the problem.

7. Practical Application: Demonstrates an application of dynamic programming and two-pointer techniques in a real-world scenario.