Trapping Rain Water

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

For example:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6 Explanation: The elevation map is represented by the array. In this case, 6 units of rain water are being trapped.

Input: height = [4,2,0,3,2,5] Output: 9

Constraints:

• n == height.length
• 1 <= n <= 2 * 10^4
• 0 <= height[i] <= 10^5

# Trapping Rain Water

This problem asks us to calculate the amount of water that can be trapped between bars of varying heights after rainfall. We are given an array of non-negative integers representing an elevation map where the width of each bar is 1.

## Naive Approach (Brute Force)

The naive approach involves iterating through each bar and, for each bar, finding the maximum height to its left and the maximum height to its right. The amount of water that can be trapped above the current bar is determined by the minimum of the maximum left and right heights, minus the height of the current bar. If this value is positive, it contributes to the total trapped water.

### Code (Brute Force)

```python
def trapping_rain_water_brute_force(heights):
    n = len(heights)
    total_water = 0

    for i in range(n):
        left_max = 0
        for j in range(i):
            left_max = max(left_max, heights[j])

        right_max = 0
        for j in range(i + 1, n):
            right_max = max(right_max, heights[j])

        water_level = min(left_max, right_max)
        if water_level > heights[i]:
            total_water += water_level - heights[i]

    return total_water

Optimal Approach (Two Pointers)

The optimal approach uses two pointers, one starting from the left and one from the right. We keep track of the maximum height seen so far from the left and the maximum height seen so far from the right. At each step, we move the pointer that points to the smaller height towards the center. The amount of water that can be trapped at the current position is determined by the difference between the maximum height seen from the corresponding side and the height of the current bar.

Code (Two Pointers)

def trapping_rain_water_two_pointers(heights):
    n = len(heights)
    if n == 0:
        return 0

    left, right = 0, n - 1
    left_max, right_max = 0, 0
    total_water = 0

    while left < right:
        if heights[left] < heights[right]:
            if heights[left] > left_max:
                left_max = heights[left]
            else:
                total_water += left_max - heights[left]
            left += 1
        else:
            if heights[right] > right_max:
                right_max = heights[right]
            else:
                total_water += right_max - heights[right]
            right -= 1

    return total_water

Example

For heights = [0,1,0,2,1,0,1,3,2,1,2,1], the function would return 6.

Big(O) Runtime Analysis

• Brute Force: The brute force approach has a time complexity of O(n^2) because, for each element, we iterate through the rest of the array to find the maximum heights on the left and right.
• Two Pointers: The two-pointers approach has a time complexity of O(n) because we iterate through the array once.

Big(O) Space Usage Analysis

• Brute Force: The brute force approach has a space complexity of O(1) because we use a constant amount of extra space.
• Two Pointers: The two-pointers approach has a space complexity of O(1) because we use a constant amount of extra space.

Edge Cases

• Empty array: If the input array is empty, the function should return 0.
• Array with only one element: If the input array has only one element, the function should return 0.
• Array with all elements equal: If all the elements in the array are equal, the function should return 0.
• Decreasing array: If the array is strictly decreasing, the function should return 0.
• Increasing array: If the array is strictly increasing, the function should return 0.