Java BFS & DFS from Ocean


  • 107
    S
    1. Two Queue and add all the Pacific border to one queue; Atlantic border to another queue.
    2. Keep a visited matrix for each queue. In the end, add the cell visited by two queue to the result.
      BFS: Water flood from ocean to the cell. Since water can only flow from high/equal cell to low cell, add the neighboor cell with height larger or equal to current cell to the queue and mark as visited.
    public class Solution {
        int[][]dir = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> res = new LinkedList<>();
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
                return res;
            }
            int n = matrix.length, m = matrix[0].length;
            //One visited map for each ocean
            boolean[][] pacific = new boolean[n][m];
            boolean[][] atlantic = new boolean[n][m];
            Queue<int[]> pQueue = new LinkedList<>();
            Queue<int[]> aQueue = new LinkedList<>();
            for(int i=0; i<n; i++){ //Vertical border
                pQueue.offer(new int[]{i, 0});
                aQueue.offer(new int[]{i, m-1});
                pacific[i][0] = true;
                atlantic[i][m-1] = true;
            }
            for(int i=0; i<m; i++){ //Horizontal border
                pQueue.offer(new int[]{0, i});
                aQueue.offer(new int[]{n-1, i});
                pacific[0][i] = true;
                atlantic[n-1][i] = true;
            }
            bfs(matrix, pQueue, pacific);
            bfs(matrix, aQueue, atlantic);
            for(int i=0; i<n; i++){
                for(int j=0; j<m; j++){
                    if(pacific[i][j] && atlantic[i][j])
                        res.add(new int[]{i,j});
                }
            }
            return res;
        }
        public void bfs(int[][]matrix, Queue<int[]> queue, boolean[][]visited){
            int n = matrix.length, m = matrix[0].length;
            while(!queue.isEmpty()){
                int[] cur = queue.poll();
                for(int[] d:dir){
                    int x = cur[0]+d[0];
                    int y = cur[1]+d[1];
                    if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < matrix[cur[0]][cur[1]]){
                        continue;
                    }
                    visited[x][y] = true;
                    queue.offer(new int[]{x, y});
                } 
            }
        }
    }
    

    DFS version:

    public class Solution {
        public List<int[]> pacificAtlantic(int[][] matrix) {
            List<int[]> res = new LinkedList<>();
            if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
                return res;
            }
            int n = matrix.length, m = matrix[0].length;
            boolean[][]pacific = new boolean[n][m];
            boolean[][]atlantic = new boolean[n][m];
            for(int i=0; i<n; i++){
                dfs(matrix, pacific, Integer.MIN_VALUE, i, 0);
                dfs(matrix, atlantic, Integer.MIN_VALUE, i, m-1);
            }
            for(int i=0; i<m; i++){
                dfs(matrix, pacific, Integer.MIN_VALUE, 0, i);
                dfs(matrix, atlantic, Integer.MIN_VALUE, n-1, i);
            }
            for (int i = 0; i < n; i++) 
                for (int j = 0; j < m; j++) 
                    if (pacific[i][j] && atlantic[i][j]) 
                        res.add(new int[] {i, j});
            return res;
        }
        
        int[][]dir = new int[][]{{0,1},{0,-1},{1,0},{-1,0}};
        
        public void dfs(int[][]matrix, boolean[][]visited, int height, int x, int y){
            int n = matrix.length, m = matrix[0].length;
            if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < height)
                return;
            visited[x][y] = true;
            for(int[]d:dir){
                dfs(matrix, visited, matrix[x][y], x+d[0], y+d[1]);
            }
        }
    }
    

  • 3
    Y

    wow, really helpful!


  • 4
    S

    @yuhengw Thanks, hope it helps ; )


  • 1
    A

    It's a good solution!


  • 2
    M

    thanks, that helps!


  • 0
    B
    This post is deleted!

  • 3
    S

    @braydenCN Thanks for sharing. Correct me if I am wrong, you only check for two direction. What if a cell can reach ocean from other two directions?


  • 0
    B

    @star1993 thanks for pointing this out! Yes, I made a mistake here.


  • 0
    I

    Can I ask the time complexity analysis of both? Thanks.


  • 3
    S

    @icezhou0784 It should be O(NM), where M N is the length and width of the matrix.


  • 0
    I

    @star1993
    Why can't it be O(m^2n) or O(n^2m)? Each time complexity of dfs would be O(mn), then there is a for loop outside, which should be O(m^2n) or O(n^2m)? Is that right?


  • 8
    S

    @icezhou0784 Correct me if I am wrong. Since we keep a visited list for each ocean, we only visit a cell if it is not visited before. For each ocean, the worst case is NM thus totally O(NM)


  • 0
    I

    @star1993
    Yes, I think you are right.


  • 0
    S

    Python Version

    class Solution(object):
        row_shift = [-1, 0, 0, 1];
        col_shift = [0, -1, 1, 0];
        
        def pacificAtlantic(self, matrix):
            if matrix == None or len(matrix) == 0: return []
            n = len(matrix)
            m = len(matrix[0])
            
            res = []
            
            pacific = [[False for j in range(0, m)] for i in range(0,n)]
            atlantic = [[False for j in range(0, m)] for i in range(0,n)]
            
            #dfs along the decreasing cell, all those cell will can reach to the 
            #pacific or atlantic oceans
            for i in range(0,n):
                self.dfs(pacific, matrix, i, 0)
                self.dfs(atlantic, matrix, i, m - 1)
            
            for j in range(0,m):
                self.dfs(pacific, matrix, 0, j)
                self.dfs(atlantic, matrix, n - 1, j)
                
            for i in range(0,n):
                for j in range(0,m):
                    if pacific[i][j] and atlantic[i][j]:
                        res.append([i,j])
            
            return res
            
        def dfs(self, dp, matrix, row, col):
            dp[row][col] = True;
            
            for k in range(0, 4):
                next_row = row + self.row_shift[k]
                next_col = col + self.col_shift[k]
                
                if (next_row >= 0 and next_row < len(matrix) and next_col >= 0 and next_col < len(matrix[0]) and 
                    (not dp[next_row][next_col]) and matrix[next_row][next_col] >= matrix[row][col]):
                        self.dfs(dp, matrix, next_row, next_col)
    

  • 0
    B

    Very Clear and Elegant Solutions! THANK YOU for sharing!


  • 0

    why this BFS solution is slower than the DFS solution?


  • 0
    K

    I have a question about the dir, what is the dir?


  • 0
    H

    @kate8528577 dir is an array used to find all 4 surrounding coordinates for given (X,Y) coordinate. Ex. if we are at (1,1) then (X,Y)+dir will give us all 4 coordinate which are at bottom , top, left and right of (1,1)


  • 0
    V

    @star1993 Do you think we can use memoization here? I know that it won't reduce the time complexity. It will still be O(mn), but memoization would avoid repeated recursive calls.


  • 1

    @VRAMJI

    I guess the original post already used memo -

    if(x<0 || x>=n || y<0 || y>=m || visited[x][y] || matrix[x][y] < height)
    return;
    

    If the cell has been visited previously, DFS simply returns. That's how it archives O(m*n).


Log in to reply
 

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