LeetCode 42 - Trapping Rain Water - 2023.04.02 solution

class Solution:
    def trap(self, height: List[int]) -> int:
        """ To solve this, we want to understand how to calculate the amount of rainwater
        trapped at each index.  Then we just need to have that information that's necessary
        to do that calculation.

        The calculation is that the amount of water is defined by the difference between
        the (minimum of the max height to the left and right of the point) and the height
        of the current index.

        So if we're going to visit each index once to do the calculation, we first need to
        know the max heights to the left and right of each point.  We can do that in two
        other passes.

        So first we'll go through and create a list of the max height to the left of each
        point, then a second time backwards to create a list of the max height to the right
        of each point, and then a final time to do the calculation.
        """
        max_height_to_the_l = [0 for h in height]
        for i, h in enumerate(height):
            if i == 0:
                continue
            max_height_to_the_l[i] = max(height[i-1], max_height_to_the_l[i-1])

        max_height_to_the_r = [0 for h in height]
        for i in range(len(height)-2, -1, -1):
            h = height[i]
            max_height_to_the_r[i] = max(height[i+1], max_height_to_the_r[i+1])

        water_at_each_index = [0 for h in height]
        for i in range(len(height)):
            brim_level = min(max_height_to_the_l[i], max_height_to_the_r[i])
            water_at_each_index[i] = max(0, brim_level - height[i])

        return sum(water_at_each_index)