[LeetCode] 42. Trapping Rain Water

Problem : https://leetcode.com/problems/trapping-rain-water/

It is intuitive that if one position can contain water, it must be on the lower level of both left and right side.

So we may iterate from left to right to find the maximum height of each bar from left.

Then iterate from right to left to find the maximum height of each bar from right.

The volume of each bar  = Min( maximum_height_from left,  maximum_height_from_right ) - bar_height.

Time Complexity = O ( N + N + N )

class Solution:
    def trap(self, height: List[int]) -> int:
        N = len(height)
        if N < 2: return 0
        
        # left[i] = maximum height from left of position i
        left = [0] * N
        mx = 0
        for i in range(N):
            left[i] = mx
            mx = max(mx, height[i])
        
        # right[i] = maximum height from right of position i
        right = [0] * N
        mx = 0
        for i in reversed(range(N)):
            right[i] = mx
            mx = max(mx, height[i])
        
        result = 0
        for i in range(N):
            # maximum water can be contained at ith position
            result += max(0, min(left[i], right[i]) - height[i])
        
        return result

Monotonic stack based solution. Time Complexity = O ( 2 * N ), because for every position it could be visited at most 2 times. 

class Solution:
    def trap(self, height: List[int]) -> int:
        
        # maintain a monotonic decreasing stack 
        stack = []
        result = 0
        
        for right in range(len(height)):
            
            # it can form a cavity if we find a taller right bar
            while stack and height[stack[-1]] < height[right]:
                bottom = stack.pop()
                
                # break if cannot find left bar
                if not stack:
                    break
                    
                left = stack[-1]
                
                # calculate the portion of water can be contained by this position
                bound_distance = right - left - 1
                bound_height = min(height[left], height[right]) - height[bottom]
                
                result += bound_distance * bound_height
                
            stack.append(right)
         
        return result

Edited on 06/18/2021. Update a more intuitive solution.

Edited on 08/01/2021. Add the monotonic stack based solution.