leetcode-42 Trapping Rain Water

[42] Trapping Rain Water

Key Concept: Two Pointers with Max Heights - Water at any position is determined by the minimum of the maximum heights on both sides minus the current height. Use two pointers to track max heights from both ends.

Algorithm: Move the pointer with smaller max height inward, as it determines the water level at that position.

# 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 elevation map traps 6 units of rain water.
#
# Example 2:
# Input: height = [4,2,0,3,2,5]
# Output: 9
#
# Constraints:
# n == height.length
# 1 <= n <= 2 * 10^4
# 0 <= height[i] <= 10^5

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

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

        while left < right:
            # Move pointer with smaller max height
            # Water level is determined by the smaller of the two max heights
            if left_max < right_max:
                left += 1
                left_max = max(left_max, height[left])
                # Water trapped at current position
                water += left_max - height[left]
            else:
                right -= 1
                right_max = max(right_max, height[right])
                water += right_max - height[right]

        return water

# Alternative approach using left and right max arrays:
class Solution2:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0

        # Precompute max heights from left and right
        left_max = [0] * n
        right_max = [0] * n

        left_max[0] = height[0]
        for i in range(1, n):
            left_max[i] = max(left_max[i - 1], height[i])

        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])

        water = 0
        for i in range(n):
            water += min(left_max[i], right_max[i]) - height[i]

        return water

# Two-pointer: Time O(n), Space O(1)
# Array approach: Time O(n), Space O(n)