Trapping Rain Water LeetCode Problem 42 [Python Solution]

Trapping Rain Water LeetCode Question: 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.

This problem asks us to compute how much rainwater can be trapped within a given elevation map represented by an array of non-negative integers.

Understanding the Problem

Imagine an elevation map where each bar has a certain height, and the width of each bar is 1.

When it rains, some areas between these bars can trap rainwater.

Our task is to calculate the total amount of rainwater that can be trapped by the elevation map.

Here’s an example:

Example 1:

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Explanation: The elevation map can trap 6 units of rainwater as shown in the black sections.

Tackling Trapping Rain Water with a Problem-Solving Approach

To solve this problem, we need to determine the amount of water that can be trapped at each position in the elevation map.

To do this, we’ll calculate the maximum height to the left and right of each position and find the minimum of these two values.

The difference between the minimum height and the actual height at the current position will give us the amount of water that can be trapped at that position.

Let’s go through the steps to solve this problem:

Constraints

Before we dive into the solution, let’s clarify the constraints:

The length of the height array, n is between 1 and 20,000.
The height of each bar in the elevation map is between 0 and 105.

Bruteforce Approach

To gain a deeper understanding of the problem, let’s start with a brute-force approach.

We’ll calculate the trapped water for each position one by one.

def trap(height):
    n = len(height)
    trapped_water = 0

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

        min_boundary = min(max_left, max_right)

        if min_boundary > height[i]:
            trapped_water += min_boundary - height[i]

    return trapped_water

This code calculates the trapped water for each position i by finding the maximum heights to the left and right of i and then determining the minimum boundary height.

If the minimum boundary height is greater than the height at 'i' we add the trapped water to our result.

However, this brute-force approach has a time complexity of O(n^2), as we calculate the maximum height to the left and right for each position 'i.'

We can optimize this to O(n) using a more efficient approach.

Efficient Approach with Two Pointers

The key to an efficient solution is to avoid redundant calculations.

Instead of calculating the maximum height to the left and right for each position, we can pre-compute these values and store them in arrays.

This reduces the time complexity to O(n).

Let’s implement this optimized approach in Python:

Trapping Rain Water Python Code Solution

View on GitHub ➹

def trap(self, height: List[int]) -> int:
    if not height:
        return 0

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

    while left &lt; right:
        if left_max &lt; right_max:
            left += 1
            left_max = max(left_max, height[left])
            trapped_water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            trapped_water += right_max - height[right]

    return trapped_water

In this code, we use two pointers, 'left' and 'right' starting from the two ends of the elevation map.

We also maintain 'left_max' and 'right_max' to keep track of the maximum heights encountered so far.

The idea is to always move the pointer with the smaller maximum height because the larger maximum height ensures that we won’t trap any additional water.

We update the trapped water accordingly as we iterate through the elevation map.

This approach has a time complexity of O(n) because we traverse the elevation map once.

Additionally, it uses constant space, making it an optimal solution for this problem.

Reasoning Behind Our Efficient Approach

To understand why this efficient approach works, let’s break down the reasoning step by step:

We start with two pointers, 'left' and 'right' at the two ends of the elevation map.
We also maintain 'left_max' and 'right_max' to keep track of the maximum heights encountered from the left and right sides, respectively. These values are initially set to the heights at the starting positions.
While 'left' is less than 'right' we compare 'left_max' and ‘right_max.’ We want to move the pointer with the smaller maximum height because that’s the side where we can potentially trap water.
If 'left_max' is less than ‘right_max,’ we move the 'left' pointer to the right and update 'left_max' to the maximum of its current value and the height at the new position.
If 'right_max' is less than or equal to ‘left_max,’ we move the ‘right’ pointer to the left and update 'right_max' in a similar manner.
For each step, we calculate the trapped water using the minimum of 'left_max' and 'right_max' (the lower boundary) minus the height at the current position. This represents the water that can be trapped at the current position.
We accumulate the trapped water as we iterate through the elevation map.
Finally, we return the total trapped water, which is our answer.

This approach ensures that we consider the correct boundaries when calculating the trapped water at each position, and it does so with the time complexity of O(n) and constant space, also called O(1) complexity.

Conclusion

And there you have the solution to the hard LeetCode problem 42, Trapping Rain Water .

We explored both a brute-force approach and an efficient approach using two-pointers.

The efficient approach optimally solves the problem in O(n) time complexity and constant space complexity.

By understanding the problem, constraints, and reasoning behind the efficient solution, we’ve learned a valuable technique for solving similar problems involving elevation maps and water trapping.

Feel free to comment, ask questions, make suggestions, and share this content with others as you continue to enhance your problem-solving skills.

Solve on LeetCode now…

Happy coding!