417_Pacific_Atlantic_Water_Flow.java

classSolution {
publicList<List<Integer>> pacificAtlantic(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
returnCollections.emptyList();
 }

List<List<Integer>> result = newArrayList<>();
introws = matrix.length, cols = matrix[0].length;

boolean[][] pacificVisited = newboolean[rows][cols];
boolean[][] atlanticVisited = newboolean[rows][cols];

for (inti = 0; i < rows; i++) {
dfs(matrix, i, 0, -1, pacificVisited);
dfs(matrix, i, cols - 1, -1, atlanticVisited);
 }

for (intj = 0; j < cols; j++) {
dfs(matrix, 0, j, -1, pacificVisited);
dfs(matrix, rows - 1, j, -1, atlanticVisited);
 }

for (inti = 0; i < rows; i++) {
for (intj = 0; j < cols; j++) {
if (pacificVisited[i][j] && atlanticVisited[i][j]) {
result.add(Arrays.asList(i, j));
 }
 }
 }

returnresult;
 }

privatevoiddfs(int[][] matrix, intx, inty, intprevWaterHeight, boolean[][] visited) {
if (x < 0 || y < 0 || x >= matrix.length || y >= matrix[x].length || visited[x][y]
 || prevWaterHeight > matrix[x][y]) {
return;
 }

intheight = matrix[x][y];
visited[x][y] = true;

dfs(matrix, x - 1, y, height, visited);
dfs(matrix, x + 1, y, height, visited);
dfs(matrix, x, y - 1, height, visited);
dfs(matrix, x, y + 1, height, visited);

return;
 }
}