Trapping Rain Water

The problem description can be found in LeetCode.

Approach

An easy way to think about this problem is to first understand how much water a single location can contain.

For each position, the amount of water is bounded to the minimum value between the maximum height on the left and on the right, minus its height. In fact, think of a single cell of height 0 with their corresponding maximum left and right heights equal to n. That cell can contain n - h = n - 0 = n amount of water.

So, a naive implementation would consist of calculating the maximum left and right and then calculate the amount of trapped water by summing up all the water that can be contained in every cell:

from typing import List


class Solution:
    def trap(self, heights: List[int]) -> int:
        max_left = [0] * len(heights)
        max_right = [0] * len(heights)

        ml = 0
        for i in range(len(heights)):
            max_left[i] = ml
            ml = max(ml, heights[i])

        mr = 0
        for i in range(len(heights) - 1, -1, -1):
            max_right[i] = mr
            mr = max(mr, heights[i])

        ans = 0
        for i in range(len(heights)):
            trapped_water = min(max_left[i], max_right[i]) - heights[i]
            ans += max(trapped_water, 0)

        return ans

This would require $O(n)$ for both time and space.

However, there is a better approach, which does not require this additional space. In fact, we only care about finding a higher height either on left or right for the single cell.

At every cell, if we increment the left pointer, it means that there is a higher height on the right. Alternatively, we could increment the right one if the left pointer points to a higher height value.

This means that we do not actually care about higher height which is either on the left or on the right. We just know that there is one, which means that the cell could contain some water.

Solution

from typing import List


class Solution:
    def trap(self, heights: List[int]) -> int:
        left, right = 0, len(heights) - 1
        left_max, right_max = heights[left], heights[right]
        ans = 0

        while left < right:
            if left_max < right_max:
                # there is a higher height on the `right`,
                # which means that the `left` pointer contains
                # a smaller value
                #
                # this would be an implicit `min(max_left[i], max_right[i])`
                # as we did in the previous implementation
                left += 1
                left_max = max(left_max, heights[left])
                ans += left_max - heights[left]
            else:
                # check the considerations above
                right -= 1
                right_max = max(right_max, heights[right])
                ans += right_max - heights[right]

        return ans

Complexity

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

Where $n$ is the size of the heights list.