# Java BFS & DFS from Ocean

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) {
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];
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])
}
}
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) {
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])
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]);
}
}
}
``````

• @yuhengw Thanks, hope it helps ; )

• It's a good solution!

• thanks, that helps!

• This post is deleted!

• @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?

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

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

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

• @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?

• @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)

• @star1993
Yes, I think you are right.

• 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)
``````

• Very Clear and Elegant Solutions! THANK YOU for sharing!

• why this BFS solution is slower than the DFS solution?

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

• @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)

• @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.

• @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).

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