Leetcode 42. Trapping Rain Water

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

My first try

My first thought is having a 2 pointer to find the higher wall and calculate the trapping water between the walls. However, if one pointer arrived the highest wall, then the pointer won’t move anymore, so it’s required to do the calculation twice in order to avoid this situation.

class Solution:
    def calculateTrapping(self, end, height):
        higher_index = 0
        lower_index = 0

        total_trapping = 0

        while lower_index < end:
            if height[higher_index] <= height[lower_index]:
                min_height = min(height[higher_index], height[lower_index])
                end_index = max(higher_index, lower_index)
                start_index = min(higher_index, lower_index)
                for index in range(start_index + 1, end_index):
                    total_trapping += min_height - height[index]
                higher_index = lower_index
            lower_index += 1
        
        return total_trapping, higher_index

    def trap(self, height: List[int]) -> int:
        prefix_trapping, higher_index = self.calculateTrapping(len(height), height)
        postfix_trapping, higher_index = self.calculateTrapping(len(height) - higher_index, height[::-1])

        return prefix_trapping + postfix_trapping

My second try

The first try was working fine but doesn’t look good enough. I also looked into people’s solutions and saw the best one is quite similar to my first try, but the concept is slightly different. The pointers start at start index (0) and end_index (len(height)), then find the higher wall and calculate the trapping water.

class Solution:
    def trap(self, height: List[int]) -> int:
        total_trapped_water = 0
        
        left_index = 0
        right_index = len(height) - 1

        left_max = height[left_index]
        right_max = height[right_index]

        while left_index < right_index:
            if left_max <= right_max:
                left_max = max(left_max, height[left_index + 1])
                total_trapped_water += left_max - height[left_index + 1]

                left_index += 1
            else:
                right_max = max(right_max, height[right_index - 1])
                total_trapped_water += right_max - height[right_index - 1]

                right_index -= 1
        
        return total_trapped_water