class Solution {
    int m, n;
    public List<List<Integer>> pacificAtlantic(int[][] matrix) {
        List<List<Integer>> res = new ArrayList<>();
        if(matrix.length == 0 || matrix[0].length == 0) return res;
        m = matrix.length;
        n = matrix[0].length;

        boolean[][] pOcean = new boolean[m][n];
        boolean[][] aOcean = new boolean[m][n];
        Queue<int[]> pQueue = new LinkedList<>();
        Queue<int[]> aQueue = new LinkedList<>();
        for(int i = 0; i < m; i++){
            pQueue.add(new int[]{i, 0});
            aQueue.add(new int[]{i, n-1});
            pOcean[i][0] = true;
            aOcean[i][n-1] = true;
        }
        for(int i = 0; i < n; i++){
            pQueue.add(new int[]{0, i});
            aQueue.add(new int[]{m-1, i});
            pOcean[0][i] = true;
            aOcean[m-1][i] = true;
        }
        bfs(aQueue, matrix, aOcean);
        bfs(pQueue, matrix, pOcean);

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(aOcean[i][j] && pOcean[i][j])    res.add(Arrays.asList(i, j));
            }
        }
        return res;
    }

    int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    private void bfs(Queue<int[]> queue, int[][] matrix, boolean[][] visited){
        while(!queue.isEmpty()){
            int[] pos = queue.poll();
            for(int[] d: dir){
                int x = pos[0] + d[0];
                int y = pos[1] + d[1];
                if(x < 0 || y < 0 || x >= m || y >= n || visited[x][y] || matrix[x][y] < matrix[pos[0]][pos[1]])    continue;
                visited[x][y] = true;
                queue.add(new int[]{x, y});
            }
        }
    }
}