Problem:
There is a rectangular island of size m * n where m is the length and n is the breadth.
The island is surrounded by Pacific Ocean on the left and the top and the Atlantic Ocean on the right and bottom.
The m * n island is divided into m * n grids .
You are given the height of each grid.
When it rains , water can flow from a grid to another grid if its size is equal to or smaller than the first grid and flow all the way to the ocean if subsequent grids (in either of the four directions) are equal or smaller in height.
You need to find out if from a given grid, water can flow both to the Pacific Ocean and the Atlantic Ocean.
For example , consider the below island:
The grids highlighted in yellow are the grids from which water can flow to both the Atlantic Ocean and the Pacific Ocean.
For example take the grid in row = 2 and column = 2 (index starting from 0)
The height of the grid is 5.
If you keep moving along the left from this grid , you can reach the Pacific Ocean as all the grids along the left are smaller than the previous ones.(heights 4 and then 2)
Also if you keep moving along the right , you can reach the Atlantic Ocean as all the grids along the right are smaller than the previous ones (heights 3 and then 1).
So [2,2] is one of the answers.
You need to return all such grids.
Try out the solution here:
https://leetcode.com/problems/pacific-atlantic-water-flow/
Solution:
Hint:
Instead of finding out whether you can move from a cell to both the oceans,
Find out if you can move from both the oceans to a particular cell .
So you have to move along increasing heights from the ocean.
If a cell can be reached from both the oceans then add it to the output.
For the above traversal from ocean to grid , you can use both BFS (Breadth First Search) and DFS(Depth First Search).
Let’s look at both the solutions:
Breadth First Search:
Remember , for BFS you use queues
For DFS you use recursion.
So in this case as well , you use two queues.
One for representing the grids that can be reached from the Pacific ocean and another from the Atlantic ocean.
First as it is obvious , all the grids touching the ocean are reachable from the ocean.
So populate the corresponding queues for these positions.
Here is the code:
numRows = heights.length;
numCols = heights[0].length;
Queue<int[]> pacificQueue = new LinkedList<>();
Queue<int[]> atlanticQueue = new LinkedList<>();
for(int i=0;i<numRows;i++){
pacificQueue.offer(new int[]{i,0});
atlanticQueue.offer(new int[]{i,numCols-1});
}
for(int i=0;i<numCols;i++){
pacificQueue.offer(new int[]{0,i});
atlanticQueue.offer(new int[]{numRows-1,i});
}
Once you populate the queues , do BFS on both of them to get the grids reachable from the ocean:
BFS:
- Pop the top element from the queue
- Mark it as reachable
- Get the grids in all four directions :
- If they exceed boundary conditions (row or column goes negative or exceeds maximum number) or if the grid is already visited or if the next grid’s height is smaller than don’t consider that grid
- Else add the grid to the queue again and continue BFS
Here is the code:
public boolean[][] bfs(Queue<int[]> q,int[][] heights){
boolean[][] reachable = new boolean[numRows][numCols];
while(!q.isEmpty()){
int[] p = q.poll();
reachable[p[0]][p[1]] = true;
for(int[] d:DIRECTIONS){
int newRow = p[0] + d[0];
int newCol = p[1] + d[1];
if(newRow<0 || newCol <0 || newRow >= numRows || newCol >= numCols){
continue;
}
if(reachable[newRow][newCol]){
continue;
}
if(heights[newRow][newCol] < heights[p[0]][p[1]]){
continue;
}
q.offer(new int[]{newRow,newCol});
}
}
return reachable;
}
Once you do BFS for both the oceans.
Check the grids which are reachable from both the oceans and add them to the output:
List<List<Integer>> output = new ArrayList<>();
for(int i=0;i<numRows;i++){
for(int j=0;j<numCols;j++){
if(pacificReachable[i][j] && atlanticReachable[i][j]){
output.add(List.of(i,j));
}
}
}
Here is the entire code:
class Solution {
int[][] DIRECTIONS = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
int numRows;
int numCols;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
if(heights.length == 0 ) return null;
numRows = heights.length;
numCols = heights[0].length;
Queue<int[]> pacificQueue = new LinkedList<>();
Queue<int[]> atlanticQueue = new LinkedList<>();
for(int i=0;i<numRows;i++){
pacificQueue.offer(new int[]{i,0});
atlanticQueue.offer(new int[]{i,numCols-1});
}
for(int i=0;i<numCols;i++){
pacificQueue.offer(new int[]{0,i});
atlanticQueue.offer(new int[]{numRows-1,i});
}
boolean[][] pacificReachable = bfs(pacificQueue,heights);
boolean[][] atlanticReachable = bfs(atlanticQueue,heights);
List<List<Integer>> output = new ArrayList<>();
for(int i=0;i<numRows;i++){
for(int j=0;j<numCols;j++){
if(pacificReachable[i][j] && atlanticReachable[i][j]){
output.add(List.of(i,j));
}
}
}
return output;
}
public boolean[][] bfs(Queue<int[]> q,int[][] heights){
boolean[][] reachable = new boolean[numRows][numCols];
while(!q.isEmpty()){
int[] p = q.poll();
reachable[p[0]][p[1]] = true;
for(int[] d:DIRECTIONS){
int newRow = p[0] + d[0];
int newCol = p[1] + d[1];
if(newRow<0 || newCol <0 || newRow >= numRows || newCol >= numCols){
continue;
}
if(reachable[newRow][newCol]){
continue;
}
if(heights[newRow][newCol] < heights[p[0]][p[1]]){
continue;
}
q.offer(new int[]{newRow,newCol});
}
}
return reachable;
}
}
Here is the algorithm:
- If heights array is empty return null
- Find number of rows and columns
- Prepare two queues to store the indices of grids which are reachable from each ocean
- Add the grids touching the oceans to the corresponding queues
- Do BFS for each ocean and get the grids which are reachable from each ocean (BFS algorithm shared already)
- Find the grids reachable from both the ocean and add them to the output
- Return output
Time complexity:
During each BFS we visit every grid exactly once. So if there are m* n grids , the time complexity is O(m * n )
Space complexity:
We use two queues , two boolean arrays to represent the output of each BFS traversal in addition to the output array. Each of them can contain maximum m * n values. So space complexity is O(m * n)
Depth First Search:
In case of depth first search as already mentioned you use recursion and keep moving to next grid from a grid if its height is greater.
So instead of doing BFS on the two queues , here you perform recursive calls from each grid touching the corresponding oceans.
Here is the code which does that:
numRows = heights.length;
numCols = heights[0].length;
boolean[][] pacificReachable= new boolean[numRows][numCols];
boolean[][] atlanticReachable = new boolean[numRows][numCols];
for(int i=0;i<numRows;i++){
dfs(i,0,pacificReachable,heights);
dfs(i,numCols-1,atlanticReachable ,heights);
}
for(int i=0;i<numCols;i++){
dfs(0,i,pacificReachable,heights);
dfs(numRows-1,i,atlanticReachable ,heights);
}
Here is the DFS code:
public void dfs(int row,int col,boolean[][] r,int[][] h){
r[row][col] = true;
for(int[] d:DIRECTIONS){
int nR = row + d[0];
int nC = col + d[1];
if(nR < 0 ||nR >= numRows || nC < 0 || nC >= numCols || r[nR][nC] || h[nR][nC] < h[row][col])
continue;
dfs(nR,nC,r,h);
}
}
DFS algorithm:
- Mark the current grid as reachable (we start from the border grid initially)
- Check in each direction if the grid is reachable from the current grid , if so do DFS recursively on each such grid.
Once you do DFS for both the oceans , find the common grids reachable from both the oceans using the output from DFS.
Here is the code:
List<List<Integer>> o = new ArrayList<>();
for(int i=0;i<numRows;i++){
for(int j=0;j<numCols;j++){
if(pR[i][j] && aR[i][j]){
o.add(List.of(i,j));
}
}
}
Here is the entire code:
class Solution {
int[][] DIRECTIONS = new int[][]{{0,1},{1,0},{0,-1},{-1,0}};
int numRows;
int numCols;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
if(heights.length == 0 ) return null;
numRows = heights.length;
numCols = heights[0].length;
boolean[][] pR = new boolean[numRows][numCols];
boolean[][] aR = new boolean[numRows][numCols];
for(int i=0;i<numRows;i++){
dfs(i,0,pR,heights);
dfs(i,numCols-1,aR,heights);
}
for(int i=0;i<numCols;i++){
dfs(0,i,pR,heights);
dfs(numRows-1,i,aR,heights);
}
List<List<Integer>> o = new ArrayList<>();
for(int i=0;i<numRows;i++){
for(int j=0;j<numCols;j++){
if(pR[i][j] && aR[i][j]){
o.add(List.of(i,j));
}
}
}
return o;
}
public void dfs(int row,int col,boolean[][] r,int[][] h){
r[row][col] = true;
for(int[] d:DIRECTIONS){
int nR = row + d[0];
int nC = col + d[1];
if(nR < 0 ||nR >= numRows || nC < 0 || nC >= numCols || r[nR][nC] || h[nR][nC] < h[row][col])
continue;
dfs(nR,nC,r,h);
}
}
}
Algorithm:
- If the input heights is empty return null
- Find number of rows and columns
- For each row invoke DFS twice for each ocean for the grids touching the corresponding ocean .
- For each column invoke DFS twice for each ocean for the grids touching the corresponding ocean
- Find the common grids from the outputs of the above DFS and add them to a list
- Return the output.
Time complexity:
Every grid is traversed exactly once.
So time complexity is O(m*n) for a m*n island.
Space complexity:
Maximum m * n recursive calls are made , so space complexity for the recursion stack is O(m * n).
Also two boolean arrays are used to store DFS output for each ocean each of space complexity O(m * n )
Total space complexity is O(m * n)
That’s it!
Leave a Reply