# Java DFS 17ms

• 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 ) {
}
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;
}
}
``````

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