42. Trapping Rain Water

Problem Link

Think of the total trapped water as sum of water collected at each index. How would you calculate the trappable water at any index? The water level is bounded by the lesser of maximum heights on left and right of given index.

One way is to create prefix arrays storing maximum left and right heights for each index and finally calculate the water trapped at each level, but that’d add \(O(n)\) space complexity. We can optimize the solution to O(1) extra space using the two-pointer technique.

Start the iteration by declaring two pointers at left (\(l\)) and right (\(r\)) end of array, along with two variables to store maximum height seen so far from given \(l\) (\(maxL\)) and \(r\) (\(maxR\)). With this information, the amount of water that can be trapped at any possible is determined by: \(water = min(maxL, maxR) - height[i]\). Now, we can move only the pointer on the side with the smaller maximum height, because that side becomes the limiting factor. For example,

• \(maxL < maxR\), then the left side limits the water level as the right side is guaranteed to have a boundary at least as tall \(maxL\) (from \(< maxR\)), hence the water trapped at \(l\) depends only on \(maxL\). \(\therefore water[l] = maxL - height[l]\) and we can move forward the \(l\) as it's considered in out result
• \(maxR <= maxL\), similarly here the right side limits the water level \(\therefore water[r] = maxR - height[r]\).

Pseudocode

• Declare two pointers for indicating current left and right position in iteration.
• Declare two variables to store the maximum left and right heights.
• Iterate over the array until we've computed water level for all cells i.e \(l<=r\).
• For each iteration,
  • if \(maxL < maxR\), we'll compute water level for l and increment the counter to next index
  • else, we'll computer water level for r and decrement the counter to next index.

Runtime Complexity

Time: \(O(n)\), since we're only iterating the nums array once.

Space: \(O(1)\), constant time from two pointers.

PythonGo

class Solution:
    def trap(self, height: List[int]) -> int:
        maxL, maxR = height[0], height[-1]
        l, r = 0, len(height)-1
        result = 0
        while l <= r:
            if height[l] < height[r]:
                maxL = max(maxL, height[l])
                result += maxL-height[l]
                l+=1
            else:
                maxR = max(maxR, height[r])
                result += maxR - height[r]
                r-=1
        return result

func trap(height []int) int {
    l, r := 0, len(height)-1
    maxL, maxR := height[l], height[r]
    var result int
    for l <= r {
        if maxL < maxR {
            maxL = max(maxL, height[l])
            result += maxL - height[l]
            l++
        } else {
            maxR = max(maxR, height[r])
            result += maxR - height[r]
            r--
        }
    }
    return result
}

---