👨‍💻 738LeetCode

Trapping Rain Water

Question

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

Example

img

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Solution

  • Failed: Russian Tetris, recursion from bottom up TLE.
  • DP. Compute max bounds first, then use min to compute amount of water.
class Solution:
    def trap(self, height: List[int]) -> int:
        if not height or len(height) == 1:
            return 0
        left_bounds = [height[0]] * len(height)
        right_bounds = [height[-1]] * len(height)
        for i in range(1, len(height)):
            left_bounds[i] = max(height[i], left_bounds[i - 1])
        for i in range(len(height) - 2, -1, -1):
            right_bounds[i] = max(height[i], right_bounds[i + 1])
        water = 0
        for i in range(1, len(height) - 1):
            water += min(left_bounds[i], right_bounds[i]) - height[i]
        return water