LeetCode 42 - Trapping Rain Water - 2023.10.11 solution

class Solution:
    def trap(self, height: List[int]) -> int:
        """ As you step through each index, to determine how much rain water is at
        that location, what information do you want to know about the rest of the
        array?  You want to know 1) what's the tallest index to the left, and 2)
        what's the tallest index to the right.  Then you want to use the minimum of
        those two numbers to determine the height of the 'walls', and then compare
        it to the height at the current index to see how much water there is.

        So the plan is: first create two supplementary lists: one that, for each
        index, keeps track of the tallest index to the left of that index, and a
        second one that, for each index, keeps track of the tallest index to the
        right of that index.
        """
        tallest_to_the_left = [0 for i in range(len(height))]
        for i in range(len(height)):
            if i == 0:
                continue
            tallest_to_the_left[i] = max(tallest_to_the_left[i-1], height[i-1])

        tallest_to_the_right = [0 for i in range(len(height))]
        for i in range(len(height)-1, -1, -1):
            if i == len(height)-1:
                continue
            tallest_to_the_right[i] = max(tallest_to_the_right[i+1], height[i+1])

        rain_water_at_each_index = [0 for i in range(len(height))]
        for i in range(len(height)):
            wall_height = min(tallest_to_the_left[i], tallest_to_the_right[i])
            if height[i] < wall_height:
                rain_water_at_each_index[i] = wall_height - height[i]

        return sum(rain_water_at_each_index)