# java dfs version. simple idea

• Based on the idea that DFS could find reachability of node in graph, we do DFS from the nodes on the 4 borders of the graph.
In the end, the nodes both reachable from Pacific and Atlantic could be found.
BTW, because the size is not exceed 150, we could use a boolean[] to mark.

``````    private int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
private boolean[] mark = new boolean[150 * 150 + 150];
private Set<Integer> touchPacific = new HashSet<>();
private List<int[]> res = new ArrayList<>();

/*
pacific: true --> find the reachability of Pacific  false: Atlantic
*/
private void reachOcean(int r, int c, int[][] matrix, boolean pacific) {
int key = r * 150 + c;
mark[key] = true;

else if (touchPacific.contains(key)) res.add(new int[]{r, c});

for (int[] d: dirs) {
int r0 = r + d[0];
int c0 = c + d[1];
if (r0 < 0 || r0 >= m || c0 < 0 || c0 >= n || mark[r0 * 150 + c0] || matrix[r0][c0] < matrix[r][c]) {
continue;
}
reachOcean(r0, c0, matrix, pacific);
}
}

public List<int[]> pacificAtlantic(int[][] matrix) {
m = matrix.length;
if (0 == m) return res;

n = matrix[0].length;
if (0 == n) return res;

// top:
for (int c = 0; c < n; ++c) {
if(!mark[c]) reachOcean(0, c, matrix, true);
}

// left:
for (int r = 0; r < m; ++r) {
if(!mark[r*150]) reachOcean(r, 0, matrix, true);
}

mark = new boolean[150 * 150 + 150];
// right:
for (int r = 0; r < m; ++r) {
if(!mark[r*150 + n - 1]) reachOcean(r, n - 1, matrix, false);
}

// bottom
for (int c = 0; c < n; ++c) {
if(!mark[(m - 1) * 150 + c]) reachOcean(m - 1, c, matrix, false);
}
return  res;
}

``````

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