G. Trapping Rain Water: Recursive Decomposition

Overview

This approach uses Divide and Conquer by recursively splitting the array at its highest peak.

Complexity

• Time: Average \(O(n \log n)\); Worst-case \(O(n^2)\) for sorted arrays

• Space: \(O(n)\) for recursion and memoization

class Solution:
    def trap(self, height):

        @cache
        def solve(l, r):
            if r - l < 2:
                return 0

            # Find highest peak
            max_idx = l + 1 + height[l+1:r].index(max(height[l+1:r]))

            # If boundaries are the highest in this range, then this range is one pool,
            # in which case calculate water directly; otherwise, split recursively
            boundary_min = min(height[l], height[r])
            if height[max_idx] < boundary_min:
                res = sum((boundary_min - h) for h in height[l+1:r])
            else:
                res = solve(l, max_idx) + solve(max_idx, r)

            return res

        return solve(0, len(height) - 1)