Given an
m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.
Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
Note:
- The order of returned grid coordinates does not matter.
- Both m and n are less than 150.
Example:
Given the following 5x5 matrix:
Pacific ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * Atlantic
Return:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
Analysis:
Initially, I was trying to iterate all position, and for each position (i,j) use DFS to see whether it can reach both Atlantic and Pacific but unfortunately it is TLE. For each position, the worst case is to visit all node of the matrix and takes O(m*n) time. So for total m*n node it takes O((m*n)^2).
If we think the problem the other way, if a position (i,j) can reach both Pacific and Atlantic, it mean there must be Pacific position (pi, pj) and Atlantic (ai, ai) which connect to (i, j). In another word, (i, j) must be in the DFS/BFS search path beginning from (pi, pj) and (ai, aj). So, if we can find all the node which can be reached from Pacific edge (row or column is 0) and Atlantic (row or column is maximum), these node are the position where water can flow to both the Pacific and Atlantic ocean.
If we think the problem the other way, if a position (i,j) can reach both Pacific and Atlantic, it mean there must be Pacific position (pi, pj) and Atlantic (ai, ai) which connect to (i, j). In another word, (i, j) must be in the DFS/BFS search path beginning from (pi, pj) and (ai, aj). So, if we can find all the node which can be reached from Pacific edge (row or column is 0) and Atlantic (row or column is maximum), these node are the position where water can flow to both the Pacific and Atlantic ocean.
void dfs(int[][] matrix, boolean[][] visited, int pre, int x, int y) {
if (x < 0 || x >= matrix.length || y <0 || y >= matrix[0].length || visited[x][y] || matrix[x][y] < pre)
return;
visited[x][y] = true;
dfs(matrix, visited, matrix[x][y], x-1, y);
dfs(matrix, visited, matrix[x][y], x+1, y);
dfs(matrix, visited, matrix[x][y], x, y-1);
dfs(matrix, visited, matrix[x][y], x, y+1);
}
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> list = new ArrayList<>();
if (matrix.length == 0)
return list;
int m = matrix.length;
int n = matrix[0].length;
boolean[][] dp1 = new boolean[m][n];
boolean[][] dp2 = new boolean[m][n];
for(int i=0; i<m; i++) { //Pacific
dfs(matrix, dp1, Integer.MIN_VALUE, i, 0); //Atlantic
dfs(matrix, dp2, Integer.MIN_VALUE, i, n-1);
}
for(int i=0; i<n; i++) {
dfs(matrix, dp1, Integer.MIN_VALUE, 0, i);
dfs(matrix, dp2, Integer.MIN_VALUE, m-1, i);
}
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
if (dp1[i][j] && dp2[i][j]) {
int[] pos = {i,j};
list.add(pos);
}
}
}
return list;
} 