pacific and atlantic water flow

fishercoder1534 · fishercoder1534 · commit ac85f2dabe75 · 2016-11-01T21:09:18.000-07:00
diff --git a/MEDIUM/src/medium/PacificAtlanticWaterFlow.java b/MEDIUM/src/medium/PacificAtlanticWaterFlow.java
@@ -0,0 +1,94 @@
+package medium;
+
+import java.util.ArrayList;
+import java.util.List;
+/**Given the following 5x5 matrix:
+
+  Pacific ~   ~   ~   ~   ~ 
+       ~  1   2   2   3  (5) *
+       ~  3   2   3  (4) (4) *
+       ~  2   4  (5)  3   1  *
+       ~ (6) (7)  1   4   5  *
+       ~ (5)  1   1   2   4  *
+          *   *   *   *   * Atlantic
+
+Return:
+
+[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).*/
+
+public class PacificAtlanticWaterFlow {
+    //looked at this post: https://discuss.leetcode.com/topic/62379/java-bfs-dfs-from-ocean
+    
+    /**One typical trick to work on 2d grid problems is to go through the border and put proper ones into a queue if using BFS.*/
+    public List<int[]> pacificAtlantic(int[][] matrix) {
+
+        List<int[]> result = new ArrayList();
+        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return result;
+        
+        int m = matrix.length, n = matrix[0].length;
+        boolean[][] pacific = new boolean[m][n];
+        boolean[][] atlantic = new boolean[m][n];
+        
+        for(int i = 0; i < m; i++){
+            dfs(matrix, pacific, Integer.MIN_VALUE, i, 0);
+            dfs(matrix, atlantic, Integer.MIN_VALUE, i, n-1);
+        }
+        
+        for(int i = 0; i < n; i++){
+            dfs(matrix, pacific, Integer.MIN_VALUE, 0, i);
+            dfs(matrix, atlantic, Integer.MIN_VALUE, m-1, i);
+        }
+        
+        for(int i = 0; i < m; i++){
+            for(int j = 0; j < n; j++){
+                if(pacific[i][j] && atlantic[i][j]){
+                    result.add(new int[]{i, j});
+                }
+            }
+        }
+        
+        return result;
+    }
+    
+    void dfs(int[][] matrix, boolean[][] visited, int height, int x, int y){
+        int m = matrix.length, n = matrix[0].length;
+        if(x < 0 || y < 0 || x >= m || y >= n || matrix[x][y] < height || visited[x][y]) return;
+        visited[x][y] = true;
+        dfs(matrix, visited, matrix[x][y], x+1, y);
+        dfs(matrix, visited, matrix[x][y], x, y+1);
+        dfs(matrix, visited, matrix[x][y], x-1, y);
+        dfs(matrix, visited, matrix[x][y], x, y-1);
+    }
+    
+    public static void main(String...args){
+        PacificAtlanticWaterFlow test = new PacificAtlanticWaterFlow();
+//        int[][] matrix = new int[][]{
+//                {1,2,2,3,5},
+//                {3,2,3,4,4},
+//                {2,4,5,3,1},
+//                {6,7,1,4,5},
+//                {5,1,1,2,4},
+//        };
+        
+//        int[][] matrix = new int[][]{//this one is correct
+//                {3,5},
+//                {4,4},
+//        };
+        
+//        int[][] matrix = new int[][]{//this one is correct
+//                {2,3,5},
+//                {3,4,4},
+//        };
+        
+        int[][] matrix = new int[][]{
+                {2,3,5},
+                {3,4,4},
+                {5,3,1},
+        };
+        List<int[]> result = test.pacificAtlantic(matrix);
+        for(int[] point : result){
+            System.out.println(point[0] + "\t" + point[1]);
+        }
+    }
+
+}
diff --git a/README.md b/README.md
@@ -3,6 +3,7 @@
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
 |441|[Arranging Coins](https://leetcode.com/problems/arrange-coins/)|[Solution](../../blob/master/EASY/src/easy/ArrangingCoins.java)| O(n)|O(1) | Easy|
 |419|[Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)|[Solution](../../blob/master/MEDIUM/src/medium/BattleshipsinaBoard.java) | O(n^2) |O(1) | Medium| DFS
+|417|[Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/)|[Solution](../../blob/master/MEDIUM/src/medium/PacificAtlanticWaterFlow.java) | O(m*n*Max(m,n)) |O(m*n) | Medium| DFS
 |415|[Add Strings](https://leetcode.com/problems/add-strings/)|[Solution](../../blob/master/EASY/src/easy/AddStrings.java)| O(n)|O(1) | Easy|
 |412|[Fizz Buzz](https://leetcode.com/problems/fizz-buzz/)|[Solution](../../blob/master/EASY/src/easy/FizzBuzz.java)| O(n)|O(1) | Easy|
 |404|[Sum of Left Leaves](https://leetcode.com/problems/sum-of-left-leaves/)|[Solution](../../blob/master/EASY/src/easy/SumofLeftLeaves.java)| O(n)|O(h) | Easy|
