37ms Java Solution using BFS

• ``````public class Solution {
public List<int[]> pacificAtlantic(int[][] matrix) {
if(matrix == null || matrix.length == 0) return new ArrayList<>();

Set<Position> pacific = findFloodArea(matrix, 0, 0, true);
Set<Position> atlantic = findFloodArea(matrix, matrix.length - 1, matrix[0].length - 1, false);

List<int[]> res = new ArrayList<>();
pacific.retainAll(atlantic);
for(Position pos: pacific) res.add(new int[]{pos.row, pos.col});
return res;
}

private Set<Position> findFloodArea(int[][] matrix, int row, int col, boolean direction) {
Set<Position> res = new HashSet<>();
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
boolean[][] visited = new boolean[matrix.length][matrix[0].length];

for(int j = 0; j < matrix[0].length; j++) {
Position tmp = new Position(row, j);
visited[tmp.row][tmp.col] = true;
}

int start = direction ? 1 : 0, end = direction ? matrix.length : matrix.length - 1;
for(int i = start; i < end; i++) {
Position tmp = new Position(i, col);
visited[tmp.row][tmp.col] = true;
}

while(!queue.isEmpty()) {
Position curr = queue.poll();
for(int[] dir: dirs) {
int newRow = curr.row + dir[0], newCol = curr.col + dir[1];
if(newRow >= 0 && newCol >= 0 && newRow < matrix.length
&& newCol < matrix[0].length && !visited[newRow][newCol]) {
Position newPos = new Position(newRow, newCol);
if(matrix[newRow][newCol] >= matrix[curr.row][curr.col]) {
visited[newPos.row][newPos.col] = true;
}
}
}
}
return res;
}

class Position {
int row, col;
public Position(int row, int col) {
this.row = row;
this.col = col;
}

public boolean equals(Object other) {
Position o = (Position)other;
return this.row == o.row && this.col == o.col;
}

public int hashCode() {
return 31 * row + col;
}

public String toString() {
return "(" + row + "," + col + ")";
}
}
}
``````

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