Given m x n island with heights, water can flow to adjacent cells if height <= current. Find all cells that can flow to both Pacific (top-left) and Atlantic (bottom-right) oceans.
Input: [[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]] → Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Reverse BFS: from ocean borders, find which cells can reach each ocean (going uphill). Intersection of both sets is the answer.
- BFS/DFS from Pacific border cells (top row + left col), mark reachable.
- BFS/DFS from Atlantic border cells (bottom row + right col), mark reachable.
- Collect cells marked by both.
import java.util.*;
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m=heights.length, n=heights[0].length;
boolean[][] pac=new boolean[m][n], atl=new boolean[m][n];
Queue<int[]> pq=new LinkedList<>(), aq=new LinkedList<>();
for (int i=0;i<m;i++){pq.offer(new int[]{i,0}); pac[i][0]=true; aq.offer(new int[]{i,n-1}); atl[i][n-1]=true;}
for (int j=0;j<n;j++){pq.offer(new int[]{0,j}); pac[0][j]=true; aq.offer(new int[]{m-1,j}); atl[m-1][j]=true;}
bfs(heights,pq,pac,m,n); bfs(heights,aq,atl,m,n);
List<List<Integer>> res=new ArrayList<>();
for (int i=0;i<m;i++) for (int j=0;j<n;j++) if (pac[i][j]&&atl[i][j]) res.add(Arrays.asList(i,j));
return res;
}
private void bfs(int[][] h, Queue<int[]> q, boolean[][] visited, int m, int n) {
int[][] dirs={{1,0},{-1,0},{0,1},{0,-1}};
while (!q.isEmpty()){
int[] cur=q.poll();
for (int[] d:dirs){int r=cur[0]+d[0],c=cur[1]+d[1];
if(r>=0&&r<m&&c>=0&&c<n&&!visited[r][c]&&h[r][c]>=h[cur[0]][cur[1]]){visited[r][c]=true;q.offer(new int[]{r,c});}}
}
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M*N)