LeetCode: 42 Trapping Rain Water

LeetCode 42: Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

Problem Description:

Given a non-negative integer array height, where each element represents the height of a bar, calculate how much water can be trapped between these bars after it rains.

Example:

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

In this example, the total amount of water that can be trapped between the bars is 6.

Solution Approach:

We can solve this problem using the two-pointer technique, where we maintain two pointers starting from the left and right ends of the array, and dynamically keep track of the maximum heights on both sides to calculate the trapped water.

Steps:

1. Initialize the pointers: Use two pointers, l starting from the left, and r starting from the right. Maintain two variables l_max and r_max to keep track of the maximum heights seen so far from the left and right, respectively.
2. Move the pointers: Compare the left and right maximum heights. If the left maximum is smaller, move the left pointer to the right, updating the left maximum and calculating the water trapped. If the right maximum is smaller or equal, move the right pointer to the left, updating the right maximum and calculating the water trapped.
3. Calculate trapped water: For each step, if the current height is less than the maximum height seen so far on that side, add the difference to the total trapped water.
4. End the loop: When the two pointers meet, the calculation is complete, and the total trapped water is returned.

Code Implementation (with detailed comments):

from typing import List

class Solution:
    def trap(self, height: List[int]) -> int:
        # If the height array is empty, no water can be trapped, return 0
        if not height:
            return 0

        # Initialize the left and right pointers at the start and end of the array
        l, r = 0, len(height) - 1
        # Initialize the maximum heights seen from the left and right
        l_max, r_max = height[l], height[r]

        # Initialize total trapped water to 0
        res = 0

        # Continue until the left and right pointers meet
        while l < r:
            # If the left maximum height is less than the right maximum height
            if l_max < r_max:
                # Move the left pointer to the right
                l += 1
                # Update the left maximum height
                l_max = max(l_max, height[l])
                # Calculate the trapped water at the current position and add it to the total
                res += l_max - height[l]
            else:
                # If the right maximum height is less than or equal to the left maximum height
                # Move the right pointer to the left
                r -= 1
                # Update the right maximum height
                r_max = max(r_max, height[r])
                # Calculate the trapped water at the current position and add it to the total
                res += r_max - height[r]

        # Return the total trapped water
        return res

Code Explanation:

1. Initialization:

   • If the height array is empty, return 0 as no water can be trapped.
   • Use two pointers l and r to start at the beginning and end of the array. Initialize l_max and r_max to keep track of the highest walls seen so far from the left and right, respectively.
   • Use a variable res to store the total amount of trapped water, starting from 0.

2. Two-pointer movement:

   • As long as the left pointer l is less than the right pointer r, continue the loop.
   • If the left maximum height l_max is smaller than the right maximum height r_max, move the left pointer to the right.
     • Update l_max to the maximum of the current l_max and the new left pointer height.
     • Calculate the trapped water at the left pointer and add it to the total.
   • If the right maximum height r_max is smaller than or equal to the left maximum height, move the right pointer to the left.
     • Update r_max to the maximum of the current r_max and the new right pointer height.
     • Calculate the trapped water at the right pointer and add it to the total.

3. End of loop:

   • When the left and right pointers meet, the loop ends, and the total trapped water res is returned.

Complexity Analysis:

• Time Complexity: O(n), where n is the length of the height array. Each element is visited at most once by the left and right pointers.
• Space Complexity: O(1), as only constant space is used for the pointers and variables.

Example Analysis:

For the input height = [0,1,0,2,1,0,1,3,2,1,2,1]:

1. Initialize the pointers: l = 0, r = 11, l_max = 0, r_max = 1.
2. Compare l_max and r_max:
   • Since l_max < r_max, move the left pointer and update l_max.
3. Continue moving the pointers and updating the trapped water as explained above, eventually resulting in a total trapped water of 6.

Summary:

The two-pointer approach effectively solves the problem by dynamically maintaining the maximum heights on both sides and calculating the trapped water at each step. This solution runs in O(n) time complexity and uses constant space, making it efficient and optimal for this problem.