Pacific Atlantic Water Flow

Share

Find cells from which water can flow to both Pacific and Atlantic oceans.

Example 1
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]]
Example 2
Input: heights=[[1]] → Output: [[0,0]]

Solution Approach

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
Java
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)