Leetcode: Pacific Atlantic Water Flow
This question is not asked too often, but I thought that it would be a good practice of both depth first search and breadth first search (DFS and BFS), and I will discuss both of these implementations here.
Here is the problem:
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 ad top edges of a matrix and the "Atlantic Ocean" touches the right and bottom edges.
Here is an example, and I will explain the reasoning for the solution below.
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).
And You got to remember the edges are the Atlantic and pacific ocean which means you need to go from one edge to another. So depth-first search would probably be the best bet for this. This is because these areas are reaching from higher ground to lower ground.
A user named star1993 (27 - 28 years old I believe?) had 2 really ingenious solutions, both for breadth-first-search and depth-first-search.
We keep 2 queues and add all the Pacific borders to 1 queue and the Atlantic borders to a different queue. We flood water to the cell. Since water can only flow from a high or equal cell to a low cell, add neighbor to cell larger or equal to in that queue and mark as visited.
First, I want to explain queue.offer() from the Java API, which can be described in this link. It offers to insert something if it doesn't violate capacity restraints, this way we don't have to manually check restraints. Quite ingenious Javascript code.
For the Breadth first search, we test each direction and see if they fit within the parameters. The queue basically has multiple direction points as a result.
Inside the main method, there should be one visited map for each ocean and 2 Queues, one for a pacific queue and Atlantic queue. You can actually implement these queues as Linked Lists because of inherited methods.
After which I start with the corner cases of the Pacific and the Atlantic Ocean. I perform breadth first search for both the pacific and Atlantic Cases and update accordingly. Okay, time for the code now.
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;
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++) {
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++){
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, k});
}
}
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});
}
}
}
}
Depth first search does something very similar with a bit of modification. Instead of offering in Depth first search, the method just invokes DFS again on all the directions and subsequently marks everything as visited. We perform DFS from every corner of the Pacific and Atlantic Ocean. And that's basically it.
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[][] atlantic = new boolean[n][m];
boolean[][] pacific = 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]);
}
}
}
We assigned MIN_VALUE to height because it is the minimum value an will satisfy conditions without interfering with any of the if checkmarks or the recursive calls.
Comments
Post a Comment