Java 2 solutions with explanation, dfs & bfs


  • 0
    M

    Use two boolean matrices, "pacific" to record which places can flow to pacific and "atlantic" which places can flow to atlantic. The intersection is the places which can flow to both ocean.

    public class Solution {
        private int M, N;
        private int[][] dirs = {{0,-1},{0,1},{-1,0},{1,0}};
        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> res = new ArrayList<>();
            if(matrix == null || matrix.length==0) return res;
            M = matrix.length;
            N = matrix[0].length;
            boolean[][] pacific = new boolean[M][N];
            boolean[][] atlantic = new boolean[M][N];
            for(int i=0; i<M; i++){
                // bfs(i, 0, pacific, matrix);
                // bfs(i, N-1, atlantic, matrix);
                dfs(i, 0, pacific, matrix);
                dfs(i, N-1, atlantic, matrix);
            }
            for(int j=0; j<N; j++){
                // bfs(0, j, pacific, matrix);
                // bfs(M-1, j, atlantic, matrix);
                dfs(0, j, pacific, matrix);
                dfs(M-1, j, atlantic, matrix);
            }
            for(int i=0; i<M; i++){
                for(int j=0; j<N; j++){
                    if(pacific[i][j]&&atlantic[i][j]){
                        int[] node = {i, j};
                        res.add(node);
                    }
                }
            }
            return res;
        }
        
        private void bfs(int x, int y, boolean[][] ocean, int[][] matrix){
            if(ocean[x][y] == true) return;
            Queue<Node> que = new LinkedList<>();
            que.offer(new Node(x, y));
            ocean[x][y] = true;
            while(!que.isEmpty()){
                Node node = que.poll();
                for(int[] dir : dirs){
                    int i = node.x + dir[0];
                    int j = node.y + dir[1];
                    if(i>=0 && i<M && j>=0 && j<N && ocean[i][j]==false && matrix[i][j]>=matrix[node.x][node.y]){
                        que.offer(new Node(i,j));
                        ocean[i][j] = true;
                    }
                }
            }
        }
        class Node{
            int x, y;
            Node(int x, int y){
                this.x = x;
                this.y = y;
            }
        }
        
        private void dfs(int x, int y, boolean[][] ocean, int[][] matrix){
            if(ocean[x][y] == true) return;
            ocean[x][y] = true;
            for(int[] dir : dirs){
                int i = x + dir[0];
                int j = y + dir[1];
                if(i>=0 && i<M && j>=0 && j<N && ocean[i][j]==false && matrix[i][j]>=matrix[x][y]){
                    dfs(i, j, ocean, matrix);
                }
            }
        }
        
    }
    
    

Log in to reply
 

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