Leetcode: Trapping Rain Water II

Trapping Rain Water II



Similar Problems:


Given an m x n matrix of positive integers representing the height of each unit cell in a 2D elevation map, compute the volume of water it is able to trap after raining.

Note:
Both m and n are less than 110. The height of each unit cell is greater than 0 and is less than 20,000.

Example:

Given the following 3x6 height map:
[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

Return 4.

Trapping Rain Water II

The above image represents the elevation map [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] before the rain.
Trapping Rain Water II

After the rain, water is trapped between the blocks. The total volume of water trapped is 4.

Github: code.dennyzhang.com

Credits To: leetcode.com

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


  • Solution:
// Blog link: https://code.dennyzhang.com/trapping-rain-water-ii
// Basic Ideas: heap
// The lowest bucket determine how much water it can hold.
//
// Start from the outer circle into the inner circles
// We explore from the lowest blocks(use min-heap)
// If unexamined bucket is small then current lowest, current bucket can hold some water
// Otherwise current bucket can't hold water
//
// Complexity: Time ?, Space ?
import "container/heap"
// https://golang.org/pkg/container/heap/

type Item struct {
  x, y, v int
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
        // We want Pop to give us the highest, not lowest, priority so we use greater than here.
        return pq[i].v < pq[j].v
}

func (pq PriorityQueue) Swap(i, j int) {
        pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
        item := x.(*Item)
        *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
        old := *pq
        n := len(old)
        item := old[n-1]
        *pq = old[0 : n-1]
        return item
}

func trapRainWater(heightMap [][]int) int {
    if len(heightMap) == 0 { return 0 }

    visited := map[string]bool{}
    h := make(PriorityQueue, 0)
        heap.Init(&h)
    // add outer bounders to min-heap
    for _, i := range []int{0, len(heightMap)-1} {
        for j := 0; j < len(heightMap[0]); j++ {
            heap.Push(&h, &Item{i, j, heightMap[i][j]})
            visited[fmt.Sprintf("%d-%d", i, j)] = true
        }
    }
    for i:=1; i<len(heightMap)-1; i++ {
        for _, j:= range []int{0, len(heightMap[0])-1} {
            heap.Push(&h, &Item{i, j, heightMap[i][j]})
            visited[fmt.Sprintf("%d-%d", i, j)] = true
        }
    }

    res := 0
    x, y := 0, 0
    key := ""
    for h.Len() != 0 {
        item := heap.Pop(&h).(*Item)
        // fmt.Println("item: ", item)
        for _, offset := range [][]int{[]int{0, 1}, []int{0, -1}, []int{1, 0}, []int{-1, 0}} {
            x, y = item.x+offset[0], item.y+offset[1]
            if x<0 || x>=len(heightMap) || y<0 || y>=len(heightMap[0]) {
                continue
            }
            key = fmt.Sprintf("%d-%d", x, y)
            if visited[key] { continue }
            visited[key] = true
            if heightMap[x][y] < item.v {
                // fmt.Println(item.x, item.y, item.v, "|", x, y, item.v - heightMap[x][y])
                res += item.v - heightMap[x][y]
                heap.Push(&h, &Item{x, y, item.v})
            } else {
                heap.Push(&h, &Item{x, y, heightMap[x][y]})
            }                                
        }
    }
    return res
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.