LeetCode: Trapping Rain Water

Posted on June 9, 2018July 26, 2020 by braindenny

Trapping Rain Water

Similar Problems:

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.

The above elevation map 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. Thanks Marcos for contributing this image!

Example:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Similar problem: Product of Array Except Self

Solution: Two pass

## https://code.dennyzhang.com/trapping-rain-water
## Basic Ideas: two pass
##
##   For each cell, how much water it can hold?
##      It depends on the left and right borders
##
## Complexity: Time O(n), Space O(n)
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        lefts = [height[i] for i in range(n)]
        for i in range(1, n):
            lefts[i] = max(lefts[i-1], height[i])

        rights = [height[i] for i in range(n)]
        for i in range(n-2, -1, -1):
            rights[i] = max(rights[i+1], height[i])

        res = 0
        for i in range(n):
            res += max(0, min(lefts[i], rights[i])-height[i])
        return res

Solution: Two pointer

## https://code.dennyzhang.com/trapping-rain-water
## Basic Ideas: two pointer
##
##   For each cell, how much water it can hold?
##      Check four bars:
##       highest left bar so far, highest right bar so far
##       bar on the left, bar on the right
##
## Complexity: Time O(n), Space O(1)
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        leftH, rightH = 0, 0
        left, right = 0, n-1
        res = 0
        while left<=right:
            if height[left]<height[right]:
                res += max(0, leftH-height[left])
                leftH = max(leftH, height[left])
                left += 1
            else:
                res += max(0, rightH-height[right])
                rightH = max(rightH, height[right])
                right -= 1
        return res

Solution: Two pass

// https://code.dennyzhang.com/trapping-rain-water
// Basic Ideas: two pass
//
//  For each cell, decide how many water it can trap
//  To figure that out, we need to know:
//    - The highest wall to the left
//    - The highest wall to the right
//
// Complexity: Time O(n), Space O(n)
func trap(height []int) int {
    left := make([]int, len(height))
    max := 0
    for i, h := range height {
        left[i] = max
        if h > max {
            max = h
        }
    }
    res := 0
    max = 0
    // from right to left
    for i:=len(height)-1; i>=0; i-- {
        // v: how much water current cell can trap
        v := left[i]
        if v>max {
            v=max
        }
        if v>height[i] {
            res += v-height[i]
        }

        if height[i] > max {
            max = height[i]
        }
    }
    return res
}

Post Views: 1