Find cells from which water can flow to both Pacific and Atlantic oceans.
Input: heights=[[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]]
Input: heights=[[1]] → Output: [[0,0]]
Multi-source BFS/DFS from ocean borders. Find intersection of cells reachable from both oceans.
- BFS/DFS from Pacific border (top+left) marking reachable cells
- BFS/DFS from Atlantic border (bottom+right) marking reachable cells
- Collect cells reachable from both
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.add(new int[]{i,0}); pac[i][0]=true; aq.add(new int[]{i,n-1}); atl[i][n-1]=true; }
for (int j = 0; j < n; j++) { pq.add(new int[]{0,j}); pac[0][j]=true; aq.add(new int[]{m-1,j}); atl[m-1][j]=true; }
bfs(heights, pq, pac); bfs(heights, aq, atl);
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[][] vis) {
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int[] d : dirs) {
int ni = cur[0]+d[0], nj = cur[1]+d[1];
if (ni>=0 && ni<h.length && nj>=0 && nj<h[0].length && !vis[ni][nj] && h[ni][nj]>=h[cur[0]][cur[1]]) {
vis[ni][nj]=true; q.add(new int[]{ni,nj});
}
}
}
}
- Time Complexity: O(m*n)
- Space Complexity: O(m*n)