_417.java

package com.fishercoder.solutions;

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 _417 {
    //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;
        int 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;
        int 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) {
        _417 test = new _417();
//        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]);
        }
    }

}