Course4all
Join us on telegram
Home/dsa/Graphs/Pacific Atlantic Water Flow

Pacific Atlantic Water Flow

Master this topic with zero to advance depth.

Pacific Atlantic Water Flow

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

Water can flow to a neighboring cell (north, south, east, west) if the neighboring cell's height is less than or equal to the current cell's height.

Return a list of grid coordinates where rain water can flow to both the Pacific and Atlantic oceans.

Visual Representation

Pacific Ocean | 1 2 2 3 2 | | 3 2 3 4 4 | | 2 4 5 3 1 | Atlantic Ocean | 6 7 1 4 5 | | 5 1 1 2 4 |
Medium

Examples

Input: heights = [[1,2,2,3,2],[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]]

Cells at these coordinates can flow to both oceans.

Approach 1

Level I: Brute Force (DFS from Every Cell)

Intuition

For every single cell in the grid, we start a traversal (DFS) to see if we can reach both the Pacific and Atlantic oceans. A cell can reach an ocean if there is a path of decreasing or equal heights to the boundary.

Thought Process

  1. For each cell (r, c):
    • Run canReachPacific(r, c) using DFS.
    • Run canReachAtlantic(r, c) using DFS.
    • If both are true, add (r, c) to results.

Why it's inefficient

We repeat the same exploration many times for neighboring cells. Many paths are re-calculated.

⏱ O((M * N)^2) - For each of MN cells, we might explore MN cells.💾 O(M * N) - Recursion stack.

Detailed Dry Run

Grid: [[1, 2], [1, 1]]

CellReach Pac?Reach Atl?Result
(0,0)Yes (Edge)No (Trapped)No
(0,1)Yes (Edge)Yes (Edge)YES
java
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();
        int R = heights.length, C = heights[0].length;
        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (canReach(heights, r, c, true, new boolean[R][C]) && 
                    canReach(heights, r, c, false, new boolean[R][C])) {
                    res.add(Arrays.asList(r, c));
                }
            }
        }
        return res;
    }
    private boolean canReach(int[][] h, int r, int c, boolean isPac, boolean[][] vis) {
        if (isPac && (r == 0 || c == 0)) return true;
        if (!isPac && (r == h.length - 1 || c == h[0].length - 1)) return true;
        vis[r][c] = true;
        int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length && !vis[nr][nc] && h[nr][nc] <= h[r][c]) {
                if (canReach(h, nr, nc, isPac, vis)) return true;
            }
        }
        return false;
    }
}
Approach 2

Level III: Optimal (DFS from Ocean Coasts)

Intuition

Instead of asking "Can this cell reach the ocean?", we ask "What cells can the ocean reach?". Water flows from high to low, so if we start at the ocean and go uphill (height >= current), we can find all reachable cells efficiently.

Thought Process

  1. Create two boolean grids: canReachPacific and canReachAtlantic.
  2. Start DFS from all Pacific boundary cells (left and top edges) and mark reachable uphill cells in canReachPacific.
  3. Start DFS from all Atlantic boundary cells (right and bottom edges) and mark reachable uphill cells in canReachAtlantic.
  4. Cells marked in both grids are the result.

Pattern: Inverse Search / Multi-Source DFS

⏱ O(M * N) - Each cell is visited twice (once for each ocean).💾 O(M * N) - For the boolean grids and recursion stack.

Detailed Dry Run

Grid: [[1,2],[1,1]]

OceanStart CellsReachable (Uphill)
Pacific(0,0),(0,1),(1,0)(0,0), (0,1), (1,0)
Atlantic(1,1),(0,1),(1,0)(1,1), (0,1), (1,0)
Intersection: (0,1), (1,0), (1,1)
java
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();
        int R = heights.length, C = heights[0].length;
        boolean[][] pac = new boolean[R][C], atl = new boolean[R][C];
        
        for (int i = 0; i < R; i++) { dfs(heights, i, 0, pac); dfs(heights, i, C - 1, atl); }
        for (int i = 0; i < C; i++) { dfs(heights, 0, i, pac); dfs(heights, R - 1, i, atl); }

        for (int r = 0; r < R; r++) {
            for (int c = 0; c < C; c++) {
                if (pac[r][c] && atl[r][c]) res.add(Arrays.asList(r, c));
            }
        }
        return res;
    }
    private void dfs(int[][] h, int r, int c, boolean[][] vis) {
        vis[r][c] = true;
        int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length && !vis[nr][nc] && h[nr][nc] >= h[r][c]) {
                dfs(h, nr, nc, vis);
            }
        }
    }
}
← Previous QuestionClone Graph
Next Question →Rotting Oranges