NUHMAN.com

Introduction

LeetCode 42: Trapping Rain Water is a challenging problem where you're tasked with calculating how much rainwater can be trapped between the bars in a given elevation map. The problem asks for an optimal solution that uses linear time and constant space.

The trick to solving this problem efficiently is to utilize the two-pointer technique, which involves scanning the array from both ends and computing the trapped water based on the minimum of the two heights at the pointers.

Problem Statement

Given an integer array height where each element represents the height of a bar at that index, calculate how much water it can trap after raining. You need to solve the problem in O(n) time complexity and O(1) space complexity.

Examples

go

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

Input: height = [4,2,0,3,2,5]
Output: 9

Approach: Two Pointer Technique

To solve this problem in O(n) time and O(1) space, we use two pointers: one starting from the left and the other from the right. By maintaining the maximum heights on both sides as we move inward, we can compute the amount of trapped water at each step.

Steps:

1. Initialize two pointers: Start with one pointer at the beginning (left) and the other at the end (right) of the array.
2. Track the maximum heights: Maintain two variables left_max and right_max to store the highest bar encountered from the left and right, respectively.
3. Move the pointers inward: Compare the heights at the left and right pointers:

• If height[left] is smaller than height[right], calculate the trapped water based on left_max, and then move the left pointer to the right.
• If height[right] is smaller or equal to height[left], calculate the trapped water based on right_max, and then move the right pointer to the left.

1. Accumulate the trapped water: For each position, the trapped water is determined by the difference between the current height and the maximum height at that position.

Go Implementation

go

func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }

    left, right := 0, len(height)-1
    leftMax, rightMax := height[left], height[right]
    waterTrapped := 0

    for left < right {
        if height[left] < height[right] {
            if height[left] >= leftMax {
                leftMax = height[left]
            } else {
                waterTrapped += leftMax - height[left]
            }
            left++
        } else {
            if height[right] >= rightMax {
                rightMax = height[right]
            } else {
                waterTrapped += rightMax - height[right]
            }
            right--
        }
    }

    return waterTrapped
}

Example Walkthrough

Example 1:

go

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

1. Initialization:

• left = 0, right = 11
• leftMax = 0, rightMax = 1
• waterTrapped = 0

1. Iteration:

• Move pointers inward, calculating the trapped water at each step:
• The total water trapped is 6.

Example 2:

go

Input: height = [4,2,0,3,2,5]

1. Initialization:

• left = 0, right = 5
• leftMax = 4, rightMax = 5
• waterTrapped = 0

1. Iteration:

• Move pointers inward, calculating the trapped water at each step:
• The total water trapped is 9.

Time and Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• Time Complexity: We iterate through the array only once, with the left and right pointers moving inward, so the time complexity is O(n), where n is the length of the height array.
• Space Complexity: The algorithm uses a constant amount of extra space, i.e., O(1), since we only use a few variables to track the pointers and the maximum heights.

Edge Cases

• Empty Array: If the input array is empty, return 0 since no water can be trapped.
• No Trapping Possible: If the array is either strictly increasing or decreasing, there will be no trapped water, so return 0.
• All Elements the Same: If all bars have the same height, no water can be trapped, so return 0.
• Single Element: If there's only one bar, no water can be trapped, so return 0.

Key Takeaways

• Two-pointer technique is a highly efficient way to solve the trapping rainwater problem, reducing the space complexity to O(1).
• By maintaining the maximum heights from both sides, we can easily compute the trapped water at each step without needing extra data structures like stacks or arrays.
• The problem is a great example of greedy algorithms, where we make a series of local decisions (choosing the smaller side) to achieve an optimal solution.