[Array] LC 42. Trapping Rain Water

Trapping Rain Water - LeetCode

Goal

• 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.

Strategy

• Find the peak (global maximum height), and split the array into left and right
• On each of the left and right arrays, keep track of the local max
• In each element within in L & R sub-array, check if the current element is larger than the existing local max; if true, update the local max
• If false → res+= Local max-current element

Complexity

• Time → O(N) as we loop through the input array once to find the peak
• Space → O(1) since we didn’t use any addition array or dictionary

Code

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height)==0:
            return 0
        
        peak = 0
        maxi = max(height)
        
        for idx, i in enumerate(height):
            if i == maxi:
                peak = idx
                break
                
        leftHigh = 0
        water = 0
        for i in range(peak):
            if height[i] > leftHigh:
                leftHigh = height[i]
            else:
                water+= leftHigh - height[i]
        
        rightHigh = 0
        
        for i in range(len(height)-1,peak,-1):
            if height[i] > rightHigh:
                rightHigh = height[i]
            else:
                water+= rightHigh - height[i]
        
        return water