add 407

fishercoder1534 · fishercoder1534 · commit c67932f43cfd · 2017-07-29T09:42:49.000-07:00
diff --git a/README.md b/README.md
@@ -202,6 +202,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |411|[Minimum Unique Word Abbreviation](https://leetcode.com/problems/minimum-unique-word-abbreviation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_411.java)| O(?)|O(?) | Hard| NP-Hard, Backtracking, Trie, Recursion
 |410|[Split Array Largest Sum](https://leetcode.com/problems/split-array-largest-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_410.java)| O(nlogn)|O(1) | Hard| Binary Search, DP
 |408|[Valid Word Abbreviation](https://leetcode.com/problems/valid-word-abbreviation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_408.java)| O(n)|O(1) | Easy|
+|407|[Trapping Rain Water II](https://leetcode.com/problems/trapping-rain-water-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_407.java)| | | Hard| Heap
 |406|[Queue Reconstruction by Height](https://leetcode.com/problems/queue-reconstruction-by-height/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_406.java)| O(nlogn)|O(1) | Medium| LinkedList, PriorityQueue
 |405|[Convert a Number to Hexadecimal](https://leetcode.com/problems/convert-a-number-to-hexadecimal/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_405.java)| O(n)|O(1) | Easy|
 |404|[Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_404.java)| O(n)|O(h) | Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_407.java b/src/main/java/com/fishercoder/solutions/_407.java
@@ -0,0 +1,88 @@
+package com.fishercoder.solutions;
+
+import java.util.PriorityQueue;
+
+/**
+ * 407. Trapping Rain Water II
+ *
+ * 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.
+
+ 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.
+
+ After the rain, water are trapped between the blocks. The total volume of water trapped is 4.
+
+ */
+public class _407 {
+    /**Reference: https://discuss.leetcode.com/topic/60418/java-solution-using-priorityqueue*/
+    public class Cell {
+        int row;
+        int col;
+        int height;
+
+        public Cell(int row, int col, int height) {
+            this.row = row;
+            this.col = col;
+            this.height = height;
+        }
+    }
+
+    public int trapRainWater(int[][] heights) {
+        if (heights == null || heights.length == 0 || heights[0].length == 0)
+            return 0;
+
+        PriorityQueue<Cell> queue = new PriorityQueue<>(1, (a, b) -> a.height - b.height);
+
+        int m = heights.length;
+        int n = heights[0].length;
+        boolean[][] visited = new boolean[m][n];
+
+        // Initially, add all the Cells which are on borders to the queue.
+        for (int i = 0; i < m; i++) {
+            visited[i][0] = true;
+            visited[i][n - 1] = true;
+            queue.offer(new Cell(i, 0, heights[i][0]));
+            queue.offer(new Cell(i, n - 1, heights[i][n - 1]));
+        }
+
+        for (int i = 0; i < n; i++) {
+            visited[0][i] = true;
+            visited[m - 1][i] = true;
+            queue.offer(new Cell(0, i, heights[0][i]));
+            queue.offer(new Cell(m - 1, i, heights[m - 1][i]));
+        }
+
+        // from the borders, pick the shortest cell visited and check its neighbors:
+        // if the neighbor is shorter, collect the water it can trap and update its height as its height plus the water trapped
+        // add all its neighbors to the queue.
+        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
+        int res = 0;
+        while (!queue.isEmpty()) {
+            Cell cell = queue.poll();
+            for (int[] dir : dirs) {
+                int row = cell.row + dir[0];
+                int col = cell.col + dir[1];
+                if (row >= 0 && row < m && col >= 0 && col < n && !visited[row][col]) {
+                    visited[row][col] = true;
+                    res += Math.max(0, cell.height - heights[row][col]);
+                    queue.offer(new Cell(row, col, Math.max(heights[row][col], cell.height)));
+                }
+            }
+        }
+
+        return res;
+    }
+}
