Trapping Rain Water hard

Problem Statement

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.

Example 1

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

Example 2

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

Steps and Explanation

The core idea is to find, for each bar, how much water it can trap. This depends on the maximum height to its left and the maximum height to its right. The water trapped above a bar is the minimum of the left and right maximums, minus the bar's height. We iterate through the array, calculating this for each bar and summing the results.

We can use two arrays, left_max and right_max, to store the maximum height to the left and right of each bar respectively. Then, we iterate through the height array, calculating the trapped water at each index using the formula: min(left_max[i], right_max[i]) - height[i].

Alternatively, we can solve this problem using two pointers, which avoids the need for extra space. We initialize two pointers, left and right, to the beginning and end of the array. We maintain left_max and right_max as variables, updating them as we move the pointers. The key is to move the pointer that points to the smaller maximum, because that's the limiting factor for water trapping at that position.

Code (Two Pointers Approach)

def trap(height):
    """
    Calculates the amount of trapped rainwater.

    Args:
      height: A list of non-negative integers representing the elevation map.

    Returns:
      The total amount of trapped rainwater.
    """
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    trapped_water = 0

    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            trapped_water += max(0, left_max - height[left])  #only add if positive
        else:
            right -= 1
            right_max = max(right_max, height[right])
            trapped_water += max(0, right_max - height[right]) #only add if positive

    return trapped_water

Code (Using extra arrays - less efficient)

def trap_extra_arrays(height):
    n = len(height)
    if n == 0:
        return 0

    left_max = [0] * n
    right_max = [0] * n
    trapped_water = 0

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

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

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

    return trapped_water

Time and Space Complexity

Two Pointers Approach:

• Time Complexity: O(n), where n is the length of the height array. We iterate through the array once.
• Space Complexity: O(1). We use a constant amount of extra space.

Using extra arrays:

• Time Complexity: O(n)
• Space Complexity: O(n) because of the left_max and right_max arrays.

The two pointers approach is generally preferred due to its better space complexity. Both approaches have the same time complexity.