Java DFS 17ms


  • 0

    The idea is to use a int[][] map to remember which grid can be reached by both ocean.
    The helper1 function uses DFS starting from the grids at top and left edge. It marks map[x][y]=1 if grid[x][y] can be reached.
    The helper2 function uses DFS starting from the grids at bottom and right edge. It marks map[x][y]=2 if grid[x][y] can be reached by both ocean.

    public class Solution {
        int[][] dirs = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
        void helper1(int x, int y, int[][] map, int[][] matrix){
            map[x][y]=1;
            for (int[] dir: dirs) {
                int nbx = x+dir[0], nby = y+dir[1];
                if (nbx >= 0 && nby >= 0 && nbx < map.length && nby < map[0].length ) {
                    if (map[nbx][nby] == 0 && matrix[nbx][nby] >= matrix[x][y] ) helper1(nbx,nby,map,matrix);
                }
            }
        }
        void helper2(int x, int y, int[][] map, int[][] matrix, List<int[]> ret){
            if ( map[x][y] == 1 ) { 
                ret.add(new int[]{x,y});
            }
            map[x][y]=2;
            for (int[] dir: dirs) {
                int nbx = x+dir[0], nby = y+dir[1];
                if (nbx >= 0 && nby >= 0 && nbx<map.length && nby < map[0].length ) {
                    if (map[nbx][nby] < 2 && matrix[nbx][nby] >= matrix[x][y] ) helper2(nbx,nby,map,matrix,ret);
                }
            }
        }
        public List<int[]> pacificAtlantic(int[][] matrix) {
            int[][] map;
            List<int[]> ret = new ArrayList<int[]>();
            if (matrix==null || matrix.length==0 ) return ret;
            map = new int[matrix.length][matrix[0].length];
            for (int i=0; i<matrix[0].length; i++){
                helper1(0, i, map, matrix);
            }
            for (int i=1; i<matrix.length; i++){
                helper1(i, 0, map, matrix);
            }
            for (int i=0; i<matrix[0].length; i++){
                helper2(matrix.length-1, i, map, matrix, ret);
            }
            for (int i=0; i<matrix.length; i++){
                helper2(i, matrix[0].length-1, map, matrix, ret);
            }
            return ret;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.