42. Trapping Rain Water

Hard

Description

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 above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:

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

Constraints:

• n == height.length
• 1 <= n <= 2 * 104
• 0 <= height[i] <= 105

Solutions

Approach: Two Pointers + DP

Time complexity: \(O(n)\)

Space complexity: \(O(n)\)

Way 1

Algorithmic Way

We define \(L[i]\) as the height of the highest bar to the left of and including the position at index \(i\), and \(R[i]\) as the height of the highest bar to the right of and including the position at index \(i\).

Therefore, the amount of rainwater that can be trapped at index \(i\) is \(min(L[i],R[i])-height[i]\).

We traverse the array to calculate \(L[i]\) and \(R[i]\), and the final answer is

\[\sum_{i=0}^{n-1} \min(L[i], R[i]) - height[i]\]

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, n is the length of the array.

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)

        #Intialization
        L = [height[0]] +  [0]*(n-1)
        R = [0]*(n-1) + [height[-1]]

        #Traverse & Compute
        for i in range(1,n):
            L[i] = max(l[i-1],height[i])
            R[n-1-i] = max(r[n-i],height[n-1-i])

        return sum(min(L[i],R[i]) - height[i] for i in range(n))

Way 2

Same Appraoch Using Tilde(~) Operator, Easy to Visulize & write

In python ~i is equivalent to -1-i.

We can iterate over the list height from the end to the beginning.

~i is used to access elements from the end of the list r in reverse order.

~(i - 1) allows us to correctly reference the previous element in the list when iterating in reverse.

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)

        # Initialization
        L = [height[0]] + [0] * (n - 1)
        R = [0] * (n - 1) + [height[-1]]

        # Traverse & Compute
        for i in range(1, n):
            L[i] = max(l[i - 1], height[i])
            R[~i] = max(r[~(i - 1)], height[~i])


        return sum(min(L[i], R[i]) - height[i] for i in range(n))

Way 3

Pythonic

Another way of writing using python built-in zip function.

Python

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)

        left = [height[0]] * n
        right = [height[-1]] * n

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

        return sum(min(l, r) - h for l, r, h in zip(left, right, height))

There could be many other solutions or approaches