LeetCode 42 - Trapping Rain Water - 2022.12.29 solution

class Solution:
    def trap(self, height: List[int]) -> int:
        """ How to solve it: To solve it in O(n) time complexity, we want to think about
        what information we need at each index to be able to answer the question for
        that index.  In this case, the amount of water trapped at each index is
        determined by the lesser of the maximum height to the left of the position and
        the maximum height to the right of the position.  So we could think to first
        construct two other lists, one containing the max height to the left of each
        index, the other containing the max height to the right of each index.  But we
        don't actually need the second one, because we can calculate the answer during
        the same pass through the input that we would've used to populate that list,
        simply maintaining a single variable ('max_height_to_the_right').  And we could
        use the same list used to store the max-height-to-the-left for our output.
        """
        if len(height) < 3:
            return 0

        # Fill out the max-height-to-the-left-of-this-index list.
        res = [0 for i in range(len(height))]
        res[0] = 0
        res[1] = height[0]
        for i in range(2, len(height)):
            res[i] = max(res[i-1], height[i-1])

        # Pass from right-to-left through the input
        max_height_to_the_right = 0
        for i in range(len(height) - 1, -1, -1):
            if i < len(height) - 1:
                max_height_to_the_right = max(max_height_to_the_right, height[i+1])

            # Calculate trapped water at i
            min_of_two_max_heights = min(res[i], max_height_to_the_right)
            res[i] = max(min_of_two_max_heights - height[i], 0)
        return sum(res)