LC42. Trapping Rain Water

Approach 1: $O(n)$ memory

class Solution:
    def trap(self, height: List[int]) -> int:
	    # Not needed necessarily as per constraints
		if not height: return 0
 
        n = len(height)
        leftMaxes, rightMaxes = [0] * n, [0] * n
 
        for i in range(1, n):
            leftMaxes[i] = max(leftMaxes[i - 1], height[i - 1])
        
        for i in range(n - 2, -1, -1):
            rightMaxes[i] = max(rightMaxes[i + 1], height[i + 1])
        
        total = 0
 
        for i in range(n):
            # -ve amount is not possible, so round to 0
            total += max(
                        min(leftMaxes[i], rightMaxes[i]) - height[i],
                        0
                     )
        
        return total

Complexity

Time: $O(n)$
Space: $O(n)$

Approach 2: Two-pointer

class Solution:
    def trap(self, height: List[int]) -> int:
        # For the ith height, the rain water that can be harvested
        # would be defined by:
        # v = max(min(max_to_the_left_of(i), max_to_the_right_of(i)) - h, 0)
 
        if not height: return 0
 
        left, right = 0, len(height) - 1
        left_max, right_max = 0, 0
        total = 0
 
        while left <= right:
            # Doesn't matter what the true right max at this point is
            # since `min()` constraints it to the smallest value
            if left_max <= right_max:
                total += max(left_max - height[left], 0)
                left_max = max(height[left], left_max)
                left += 1
            else:
                total += max(right_max - height[right], 0)
                right_max = max(height[right], right_max)
                right -= 1
        
        return total

Complexity

Time: $O(n)$
Space: $O(1)$