42. Trapping Rain Water

• categories: Code, Interview Question, leetcode, Hard
• source: https://leetcode.com/problems/trapping-rain-water
• topics: Two Pointers

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.

Idea

Go forward and add when see a higher bar, in the end reverse and go backward to last bar

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = 0
        i = 0
        start = None
        local_heights_sum = 0
 
        while i < len(height):
            # Find first bar
            if start is None:
                if height[i] > 0:
                    start = i
                i += 1 
                continue
 
            # Calculate water if second bar found
            if height[i] >= height[start]:        
                ans += (i - start - 1) * height[start]
                ans -= local_heights_sum
                start = i
                i += 1
                local_heights_sum = 0
                continue
            else:
                local_heights_sum += height[i] 
 
            # In the end reverse the order and return to the last found bar
            if i == len(height) - 1:
                height = [height[i] for i in range(len(height) - 1, start-1, -1)]
                local_heights_sum = 0
                i = 1
                start = 0
                continue
            i += 1
 
        return ans