public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new ArrayList<>();
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
int m = matrix.length, n = matrix[0].length;
boolean[][] pVisited = new boolean[m][n];
boolean[][] aVisited = new boolean[m][n];
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for (int i = 0; i < m; i++) {
searchByBFS(matrix, i, 0, pVisited, directions);
searchByBFS(matrix, i, n - 1, aVisited, directions);
for (int j = 0; j < n; j++) {
searchByBFS(matrix, 0, j, pVisited, directions);
searchByBFS(matrix, m - 1, j, aVisited, directions);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pVisited[i][j] && aVisited[i][j]) {
res.add(new int[] {i, j});
public void searchByBFS(int[][] matrix, int i, int j, boolean[][] visited, int[][] directions) {
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {i, j});
while (!queue.isEmpty()) {
int[] curCell = queue.remove();
int curRow = curCell[0], curCol = curCell[1];
for (int[] direction : directions) {
int nextRow = curRow + direction[0];
int nextCol = curCol + direction[1];
if (isValid(matrix, curRow, curCol, nextRow, nextCol, visited)) {
visited[nextRow][nextCol] = true;
queue.add(new int[] {nextRow, nextCol});
public boolean isValid(int[][] matrix, int curRow, int curCol, int nextRow, int nextCol, boolean[][] visited) {
return nextRow >= 0 && nextRow < matrix.length && nextCol >= 0 && nextCol < matrix[0].length && !visited[nextRow][nextCol] && matrix[curRow][curCol] <= matrix[nextRow][nextCol];