LeetCode Solutions Blog

Trapping Rain Water

Number: 42

Difficulty: Hard

Paid? No

Problem Description

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

Key Insights

The water trapped at any index is determined by the minimum of the maximum height on its left and right minus the height at that index.
A two-pointers approach can efficiently solve the problem in one pass by maintaining left and right boundaries.
Alternative approaches include dynamic programming with pre-computed left max and right max arrays, or using a monotonic stack to determine boundaries.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) when using the two-pointer approach

Solution

We use a two-pointers strategy by initializing pointers at the beginning and the end of the array. Keep track of the maximum height seen so far from the left (left_max) and the right (right_max). At each step, move the pointer with the lesser height because the water trapped is determined by the shorter boundary. Compute the water at that position as the difference between the boundary (left_max or right_max) and the current height, accumulating it into the total. This approach ensures linear time scanning with constant extra space.

Code Solutions

# Python solution using the two pointers approach
def trap(height):
    # Initialize left and right pointers and water accumulator
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    
    # Traverse the elevation map from both ends
    while left < right:
        # Update left_max and right_max as we encounter new bars
        if height[left] < height[right]:
            # left side is the determining side
            if height[left] >= left_max:
                left_max = height[left]  # update left max since current height is higher
            else:
                water += left_max - height[left]  # water trapped at left position
            left += 1  # move left pointer to the right
        else:
            # right side is the determining side
            if height[right] >= right_max:
                right_max = height[right]  # update right max since current height is higher
            else:
                water += right_max - height[right]  # water trapped at right position
            right -= 1  # move right pointer to the left
    return water

# Example usage:
print(trap([0,1,0,2,1,0,1,3,2,1,2,1]))  # Expected output: 6