42. Trapping Rain Water

Description:

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.

 

'''
[1] brute force)

idea::
1.calculate the amount of water on the each box.
2. to calculate, need to check max height of box on the left-side and the right-side.
3. water on the box at array[i] = min(max_left, max_right) - height[i]
4-1. if water value <0, then 0
5. sum all

code::
def trap(self, height: List[int]) -> int:

    def findLeftMax(idx):
        left_max=0
        for i in range(0,idx):
            left_max=max(left_max,height[i])
        return left_max

    def findRightMax(idx):
        right_max=0
        for i in range(idx+1,len(height)):
            right_max=max(right_max,height[i])
        return right_max

    water=0
    for i in range(len(height)):
        left_max=findLeftMax(i)
        right_max=findRightMax(i)

        cur_water=min(left_max,right_max)-height[i]
        if cur_water>0:
            water+=cur_water

    return water

-T/C: O(n^2)
-S/C: O(1)
'''
'''
[2] dp - efficient solution)

idea::
not finding left and right max, store both

code::
def trap(self, height: List[int]) -> int:
    left_max=[0 for _ in range(len(height))]
    right_max=[0 for _ in range(len(height))]

    # left_max
    cur_max=0
    for i in range(len(height)):
        left_max[i]=cur_max
        cur_max=max(cur_max,height[i])

    # right_max
    cur_max=0
    for i in range(len(height)-1,-1,-1):
        right_max[i]=cur_max
        cur_max=max(cur_max,height[i])

    # sum all
    water=0
    for i in range(len(height)):
        cur_water=min(left_max[i],right_max[i])-height[i]
        if cur_water>0:
            water+=cur_water

    return water

-T/C: O(n) # three-pass
-S/C: O(n) # for left_max and right_max
'''

'''
[3] optimization)

idea::
not storing left_max and right_max, just use max' index

code::
(below)

-T/C: O(n) # two pass
-S/C: O(1)
'''

class Solution:
    def trap(self, height: List[int]) -> int:
        water=0
        
        # find max_idx and max_val
        max_idx=0
        max_val=0
        for i in range(1,len(height)):
            if max_val<height[i]:
                max_val=height[i]
                max_idx=i
        
        # cal water from left to max_idx
        left_left_max=0
        left=0
        while left<max_idx:
            cur_water=min(left_left_max,max_val)-height[left]
            if cur_water>0:
                water+=cur_water
            left_left_max=max(height[left],left_left_max)
            left+=1
        
        right_right_max=0
        right=len(height)-1
        while right>=max_idx:
            cur_water=min(right_right_max,max_val)-height[right]
            if cur_water>0:
                water+=cur_water
            right_right_max=max(height[right],right_right_max)
            right-=1
        
        return water