Leetcode 42 - Trapping Rain Water

Difficulty: hard

Table of Contents

Open Table of Contents

Problem

Given n non-negative integers representing an elevation map where the width of each bar is 1, the task is to 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: 6 units of rainwater are trapped.

Example 2:

Input: height = [4,2,0,3,2,5]
Output: 9
Explanation: 9 units of rainwater are trapped.

Constraints:

Explanation/Approach

This problem asks for the total amount of rainwater that can be trapped within the given elevation map. There are several ways to approach this problem:

Two-Pointer Approach:

Dynamic Programming Approach:

Using a Stack:

Solution: Two-Pointer Approach

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

        # Initialize two pointers for scanning the height array from both ends.
        left, right = 0, len(height) - 1

        # Initialize left_max and right_max to keep track of the maximum height seen so far
        # from the left and right sides, respectively.
        left_max, right_max = height[left], height[right]

        # Initialize a variable to accumulate the total amount of trapped water.
        trapped_water = 0

        # Loop through the height array until the left and right pointers meet.
        while left < right:
            # If the maximum height on the left is less than the maximum on the right,
            # process the left side.
            if left_max < right_max:
                left += 1  # Move the left pointer to the right.
                left_max = max(left_max, height[left])  # Update the left_max if necessary.
                trapped_water += left_max - height[left]  # Add trapped water above the current bar.
            # Otherwise, process the right side.
            else:
                right -= 1  # Move the right pointer to the left.
                right_max = max(right_max, height[right])  # Update the right_max if necessary.
                trapped_water += right_max - height[right]  # Add trapped water above the current bar.

        # Return the total amount of trapped water.
        return trapped_water

Time and Memory Complexity

The time complexity is O(n), where n is the number of elements in height, as we pass through the array only once. The space complexity is O(1), as we only use constant extra space.

Explanation

Initialization:

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

While left < right: If left_max <= right_max, move left pointer to the right. Else, move right pointer to the left. Calculating Trapped Water:

Update left_max and right_max. Add min(left_max, right_max) - height[current] to trapped_water.

Visual Representation

Initial Configuration:

    Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    Left Pointer (L): At index 0
    Right Pointer (R): At index 11
    left_max = 0, right_max = 1
    Trapped Water = 0

Iteration Steps:

  1. Step 1:

    L
v
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
                                  ^
                                   R
left_max = 0, right_max = 1
Trapped Water = 0 (No trapping as left_max < height[L])

  2. Step 2:

        L
    v
[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
                                  ^
                                   R
left_max = 1, right_max = 1
Trapped Water = 0 + 0 = 0

  3. Continuing the Process:

    Moving L and R towards each other, updating left_max and right_max.
Calculating trapped water at each step.

Solution: Dynamic Programming Approach

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

        n = len(height)
        # Initialize two lists to store the maximum height of bars to the left and right of each bar.
        left_max = [0] * n
        right_max = [0] * n

        # Fill the left_max list. For each bar, store the maximum height observed so far from the left.
        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i-1], height[i])

        # Fill the right_max list. For each bar, store the maximum height observed so far from the right.
        right_max[n-1] = height[n-1]
        for i in range(n-2, -1, -1):
            right_max[i] = max(right_max[i+1], height[i])

        # Calculate the trapped water for each bar.
        trapped_water = 0
        for i in range(n):
            # The water trapped on top of the current bar is the minimum of the maximum heights
            # to its left and right, minus the height of the bar itself.
            trapped_water += min(left_max[i], right_max[i]) - height[i]

        # Return the total amount of trapped water.
        return trapped_water

Time and Memory Complexity

The time complexity is O(n), and the space complexity is O(n) for storing the left_max and right_max arrays.

Explanation

This approach precomputes the maximum height to the left and right of every element. The trapped water at each position is the minimum of these two heights minus the height of the bar itself.

Initial Configuration:

    Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    left_max: [0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3]
    right_max: [3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 2, 1]

Calculation of Trapped Water:

Solution: Using a Stack

class Solution:
    def trap(self, height: List[int]) -> int:
        # Initialize an empty stack and a variable for trapped water.
        stack = []
        trapped_water = 0

        # Iterate through each bar in the height array.
        for i, h in enumerate(height):
            # If there's a bar that can trap water (i.e., a bar taller than the last one on the stack),
            # we calculate the trapped water.
            while stack and height[stack[-1]] < h:
                # Pop the top element from the stack.
                top = stack.pop()

                # If the stack is empty after popping, break out of the loop.
                if not stack:
                    break

                # Calculate the distance between the current bar and the bar at the new top of the stack.
                distance = i - stack[-1] - 1

                # Calculate the bounded height which is the min height of two sides minus the height of the top bar.
                bounded_height = min(height[stack[-1]], h) - height[top]

                # Add the trapped water for this portion.
                trapped_water += distance * bounded_height

            # Append the current index to the stack.
            stack.append(i)

        # Return the total amount of trapped water.
        return trapped_water

Time and Memory Complexity

The time complexity is O(n), and the space complexity is O(n) for the stack.

Explanation

The stack is used to keep track of the bars. When we find a bar that is taller than the one on top of the stack, we calculate the trapped water between them.

Visual Representation

Initial Configuration:

    Elevation Map: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    Stack: []
    Trapped Water = 0

Iteration Steps:

  1. Pushing bars onto the stack:

    For each bar, if it is not higher than the bar at the top of the stack, push its index onto the stack.

  2. Calculating Trapped Water:

    When encountering a taller bar:
- Pop the stack and calculate the water trapped with the current bar.
- Calculate the distance and bounded height.
- Add to Trapped Water.