Leetcode: Trapping Rain Water

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.
Trapping Rain Water
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
// Blog link: https://code.dennyzhang.com/trapping-rain-water
// Basic Ideas: leftrightpass
// For each cell, find the left maximum and right maximum
// Then caculate how much water current cell can hold
//
// Sapmle Data:
//    0,1,0,2,1,0,1,3,2,1,2,1
//    3,3,3,3,3,3,3,3,2,2,2,1
//    0,1,1,2,2,2,2,3,3,3,3,3
// Complexity: Time O(n), Space O(n)
func trap(height []int) int {
    lmax_list := make([]int, len(height))
    rmax_list := make([]int, len(height))
    max := 0
    // from left to right
    for i:=0; i<len(height); i++ {
        if height[i] > max { max = height[i] }
        lmax_list[i] = max
    }
    // from right to left
    max = 0
    for i:= len(height)-1; i>=0; i-- {
        if height[i] > max { max = height[i] }
        rmax_list[i] = max
    }
    // collect result
    res, border := 0, 0
    for i:=1; i<len(height)-1; i++ {
        border = lmax_list[i]
        if rmax_list[i] < border { border = rmax_list[i] }
        if height[i] < border { res += border-height[i] }
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.