LC042 - Trapping Rain Water

Problem

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

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.

Solution

Time complexity of this solution is $O(n)$, with no extra space used.

def trap(self, height: List[int]) -> int:
	# case empty
	if not height:
		return 0

	res = 0
	left = 0
	right = len(height) - 1

	maxL, maxR = height[left], height[right]

	while left < right:
		if maxL < maxR:
			res += maxL - height[left]
			left += 1
			maxL = max(maxL, height[left])
		else:
			res += maxR - height[right]
			right -= 1
			maxR = max(maxR, height[right])
	
	return res