# Java beat 90% solution

• My ides is sample, let water flow from four directions to the entire matrix, maintain a visited map for Pacific Ocean (left direction or top direction) and refresh it for Atlantic Ocean (from bottom direction or right direction). Then maintain a counter map, for each unvisited cell the flow reaches, increment its value by 1. Then we just need to find the cell with a value of 2, that's the cell that can both flow to Pacific Ocean and Atlantic Ocean.

``````public class Solution {
static final int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> result = new ArrayList<int[]>();
if(matrix.length == 0) return result;
boolean[][] visited = new boolean[matrix.length][matrix[0].length];
int[][] waterFlowCount = new int[matrix.length][matrix[0].length];
for(int i = 0; i < matrix[0].length; i++){ // from top row
dfs(matrix,0,i,visited, waterFlowCount);
}
for(int i = 0; i < matrix.length; i++){ // from left
dfs(matrix,i,0,visited, waterFlowCount);
}

visited = new boolean[matrix.length][matrix[0].length];
for(int i = 0; i < matrix[0].length; i++){ // from bottom
dfs(matrix,matrix.length-1,i,visited, waterFlowCount);
}
for(int i = 0; i < matrix.length; i++){ // from right
dfs(matrix,i,matrix[0].length-1,visited, waterFlowCount);
}

for(int i = 0; i < waterFlowCount.length; i++){
for(int j = 0; j < waterFlowCount[0].length; j++){
if(waterFlowCount[i][j] == 2)
}
}

return result;
}

public void dfs(int[][] matrix, int i, int j, boolean[][] visited, int[][] waterFlowCount){
if(i >= matrix.length || i < 0 || j >= matrix[0].length || j < 0 || visited[i][j]) {
return;
}
visited[i][j] = true;
waterFlowCount[i][j]++;
for(int[] dir : dirs){
int nexti = i + dir[0];
int nextj = j + dir[1];
if(nexti >= 0 && nexti < matrix.length && nextj >= 0 && nextj < matrix[0].length && !visited[nexti][nextj] ) {
if(matrix[nexti][nextj] >= matrix[i][j]) dfs(matrix,nexti,nextj,visited,waterFlowCount); // has to be higher than the height of itself so when water poured on this cell can reach the ocean
}
}
}
}
``````

• good idea, I made a bit improvement:)

``````static final int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> result = new ArrayList<int[]>();
if(matrix.length == 0) return result;
int n = matrix.length, m = matrix[0].length;
int[][] waterFlowCount = new int[n][m];
for(int i = 0; i < m; i++) dfs(matrix,0,i,waterFlowCount,Integer.MIN_VALUE, true, result);
for(int i = 0; i < n; i++) dfs(matrix,i,0,waterFlowCount,Integer.MIN_VALUE, true, result);
for(int i = 0; i < m; i++) dfs(matrix,n-1,i,waterFlowCount,Integer.MIN_VALUE, false, result);
for(int i = 0; i < n; i++) dfs(matrix,i,m-1,waterFlowCount,Integer.MIN_VALUE, false, result);
return result;
}
public void dfs(int[][] matrix, int x, int y, int[][] waterFlowCount, int prevheight, boolean pacific, List<int[]> result){
int n = matrix.length, m = matrix[0].length;
if(x<0||x>=n||y<0||y>=m||prevheight>matrix[x][y]) return;
if(pacific){// from top/left