Simple commented java solution with thinking progress O(n)

• ``````/*
1.Naive solution:
Standard dfs, which means for each point, we check if it can reach both pacific and atlantic,
for each point, we can possibly check all the rest of points, O(m*n * m*n)

2.A little improvement:
What about we 4 hash tables, they keep track of all the points we know so far that
can reach atlantic
cannot reach atlantic
can reach pacific
cannot reach pacific
It's doable, still hit TLE, although I didn't hit TLE when not submitting the code, but running it using the provided testing environment

3.On the other hand, we can consider the flip side
We can let the pacific and atlantic ocean "flow into" the matrix as much as possible,
using 2 boolean arrays, one for each ocean.
The result are the points that are true in both boolean table
*/

public class Solution {
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> result = new ArrayList<int[]>();
if(matrix.length == 0 || matrix[0].length == 0) return result;
boolean[][] pacific = new boolean[matrix.length][matrix[0].length];  // the pacific boolean table
boolean[][] atlantic = new boolean[matrix.length][matrix[0].length]; // the atlantic booean table
//initially, all the top and left cells are flooded with pacific water
//and all the right and bottom cells are flooded with atlantic water
for(int i = 0; i < matrix.length; i++){
pacific[i][0] = true;
atlantic[i][matrix[0].length-1] = true;
}
for(int i = 0; i < matrix[0].length; i++){
pacific[0][i] = true;
atlantic[matrix.length-1][i] = true;
}
//we go around the matrix and try to flood the matrix from 4 side.
for(int i = 0; i < matrix.length; i++){
boolean[][] pacificVisited = new boolean[matrix.length][matrix[0].length];
boolean[][] atlanticVisited = new boolean[matrix.length][matrix[0].length];
water(pacific, pacificVisited, matrix, i,0);
water(atlantic, atlanticVisited, matrix, i, matrix[0].length - 1);
}
for(int i = 0; i < matrix[0].length; i++){
boolean[][] pacificVisited = new boolean[matrix.length][matrix[0].length];
boolean[][] atlanticVisited = new boolean[matrix.length][matrix[0].length];
water(pacific, pacificVisited, matrix, 0,i);
water(atlantic, atlanticVisited, matrix, matrix.length - 1, i);
}
//check the shared points among 2 tables
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
if(pacific[i][j] && atlantic[i][j]){
int[] element = {i,j};
}
}
}
return result;
}
//the flood function
private void water(boolean[][] wet, boolean[][] visited, int[][] matrix, int i , int j){
wet[i][j] = true;
visited[i][j] = true;
int[] x = {0,0,1,-1};
int[] y = {1,-1,0,0};
for(int k = 0; k < 4; k++){
if(i+y[k] >= 0 && i+y[k] < matrix.length && j+x[k] >= 0 && j+x[k] < matrix[0].length
&& !visited[i+y[k]][j+x[k]] && matrix[i+y[k]][j+x[k]] >= matrix[i][j]){
water(wet, visited, matrix, i+y[k], j+x[k]);
}
}
}
}````

P.S Sometimes you choose an option just because the alternative is just worse.....``````

• I think you don't need to initialize the boundaries, since every time you enter the water function, you just set the value to true.

• "Sometimes you choose an option just because the alternative is just worse"

------Donald Trump

• Obviously the O(n) claim in your title is wrong, as that's impossible. Typical Trump...

• @StefanPochmann "What does N represent" is question you should ask before claiming I'm wrong. Typical trump hater.

• @StefanPochmann "What does N represent" is question you should ask before claiming I'm wrong. Typical trump hater.

Not N but n. And n is the number of columns. I don't need to ask. It's defined in the problem specification. And you yourself even correctly wrote "O(m*n * m*n)" for the "naive solution".

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