Trapping Rain Water in Python (Time Complexity: O(n))

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

 

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Understanding the Problem

The core challenge of this problem is to determine how much water can be trapped between the bars of the elevation map after it rains. This problem is significant in various fields such as civil engineering for designing drainage systems and computer graphics for simulating realistic environments.

Potential pitfalls include misunderstanding how water is trapped between bars and not accounting for all possible trapped water units.

Approach

To solve this problem, we need to consider the height of the bars and how they form valleys where water can be trapped. Here are the steps to approach the solution:

Naive Solution

The naive solution involves iterating through each bar and calculating the trapped water by finding the maximum height to the left and right of each bar. This approach is not optimal because it requires O(n^2) time complexity due to the nested loops.

Optimized Solution

We can optimize the solution using two pointers and precomputed arrays for the maximum heights to the left and right of each bar. This reduces the time complexity to O(n).

Two-Pointer Approach

In this approach, we use two pointers, one starting from the left and the other from the right. We also maintain two variables to store the maximum heights encountered so far from both directions. By comparing the heights at the pointers, we can determine the trapped water at each step.

Algorithm

Here is a step-by-step breakdown of the two-pointer algorithm:

1. Initialize two pointers, left and right, at the beginning and end of the array, respectively.
2. Initialize two variables, left_max and right_max, to store the maximum heights encountered so far from the left and right.
3. While the left pointer is less than the right pointer, do the following:
   • If the height at the left pointer is less than or equal to the height at the right pointer:
     • If the height at the left pointer is greater than or equal to left_max, update left_max.
     • Otherwise, add the difference between left_max and the height at the left pointer to the total trapped water.
     • Move the left pointer to the right.
   • Otherwise:
     • If the height at the right pointer is greater than or equal to right_max, update right_max.
     • Otherwise, add the difference between right_max and the height at the right pointer to the total trapped water.
     • Move the right pointer to the left.

Code Implementation

def trap(height):
    # Initialize pointers and variables to store max heights
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water_trapped = 0

    # Loop until the two pointers meet
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]  # Update left_max
            else:
                water_trapped += left_max - height[left]  # Calculate trapped water
            left += 1  # Move left pointer to the right
        else:
            if height[right] >= right_max:
                right_max = height[right]  # Update right_max
            else:
                water_trapped += right_max - height[right]  # Calculate trapped water
            right -= 1  # Move right pointer to the left

    return water_trapped

# Example usage
height1 = [0,1,0,2,1,0,1,3,2,1,2,1]
height2 = [4,2,0,3,2,5]
print(trap(height1))  # Output: 6
print(trap(height2))  # Output: 9

Complexity Analysis

The time complexity of the two-pointer approach is O(n) because we traverse the array only once. The space complexity is O(1) as we use a constant amount of extra space.

Edge Cases

Potential edge cases include:

• Arrays with no bars or only one bar, which should return 0 trapped water.
• Arrays with all bars of the same height, which should also return 0 trapped water.

Examples:

height = [1]
Output: 0

height = [2, 2, 2, 2]
Output: 0

Testing

To test the solution comprehensively, include a variety of test cases:

• Simple cases with small arrays.
• Complex cases with large arrays and varying heights.
• Edge cases as discussed above.

Example test cases:

assert trap([0,1,0,2,1,0,1,3,2,1,2,1]) == 6
assert trap([4,2,0,3,2,5]) == 9
assert trap([1]) == 0
assert trap([2, 2, 2, 2]) == 0

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Break down the problem into smaller parts and understand the requirements.
• Think about different approaches and their trade-offs.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the problem of trapping rainwater, explored different approaches to solve it, and provided a detailed explanation of the optimized two-pointer solution. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

We encourage readers to practice and explore further to enhance their understanding and proficiency.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode Problem: Trapping Rain Water
• GeeksforGeeks: Trapping Rain Water
• Coursera: Algorithms Part I