# Pacific Atlantic Water Flow
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/pacific-atlantic-water-flow)
Canonical: https://scaleengineer.com/dsa/problems/pacific-atlantic-water-flow
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Array, Matrix
**Companies:** [Nutanix](https://scaleengineer.com/companies/nutanix), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Coupang](https://scaleengineer.com/companies/coupang)
---
## Problem
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.

The island is partitioned into a grid of square cells. You are given an `m x n` integer matrix `heights` where `heights[r][c]` represents the **height above sea level** of the cell at coordinate `(r, c)`.

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is **less than or equal to** the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return _a **2D list** of grid coordinates_ `result` _where_ `result[i] = [ri, ci]` _denotes that rain water can flow from cell_ `(ri, ci)` _to **both** the Pacific and Atlantic oceans_.

**Example 1:**

![](https://assets.glich.co/dsa/pacific-atlantic-water-flow/image0.jpg) 

**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]]
**Explanation:** The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

**Example 2:**

**Input:** heights = [[1]]
**Output:** [[0,0]]
**Explanation:** The water can flow from the only cell to the Pacific and Atlantic oceans.

**Constraints:**

* `m == heights.length`
* `n == heights[r].length`
* `1 <= m, n <= 200`
* `0 <= heights[r][c] <= 105`

# Approaches
## Brute-Force DFS from Each Cell
This approach directly simulates the water flow for each individual cell on the island. We iterate through every cell `(r, c)` and, for each one, perform a search, such as Depth-First Search (DFS), to determine if water from this specific cell can find a path to both the Pacific and Atlantic oceans.
**Time:** O((m*n)^2). For each of the `m*n` cells, we perform a DFS. In the worst-case scenario, the DFS might have to visit all `m*n` cells. This leads to a quadratic time complexity. · **Space:** O(m*n). For each of the `m*n` starting cells, a new `visited` matrix of size `m*n` is created. The recursion stack for the DFS can also go up to `m*n` deep in the worst case.
**Pros:** Conceptually straightforward as it directly models the question's premise.
**Cons:** Extremely inefficient due to massive amounts of redundant computation. The same paths are explored repeatedly for different starting cells.; Will likely result in a 'Time Limit Exceeded' (TLE) error for larger grid sizes.
### Explanation
The algorithm iterates through every single cell of the `heights` matrix. For each cell, it initiates a new traversal (like DFS or BFS) to explore all possible paths water could take flowing downwards. A `visited` array is used for each traversal to prevent getting stuck in cycles. During a traversal starting from `(r, c)`, we keep track of whether we have reached a Pacific-bordering cell (top or left edge) and an Atlantic-bordering cell (bottom or right edge). If paths to both oceans are found, the starting cell `(r, c)` is added to the result list, and we move on to test the next cell in the grid.

```java
class Solution {
    int m, n;
    int[][] heights;
    int[] dr = {-1, 1, 0, 0};
    int[] dc = {0, 0, -1, 1};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        this.m = heights.length;
        if (m == 0) return new ArrayList<>();
        this.n = heights[0].length;
        if (n == 0) return new ArrayList<>();
        
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // For each cell, run a DFS to check reachability to both oceans
                boolean[] reaches = new boolean[2]; // reaches[0] for Pacific, reaches[1] for Atlantic
                dfs(i, j, new boolean[m][n], reaches);
                if (reaches[0] && reaches[1]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        return result;
    }

    private void dfs(int r, int c, boolean[][] visited, boolean[] reaches) {
        if (visited[r][c]) {
            return;
        }
        visited[r][c] = true;

        if (r == 0 || c == 0) {
            reaches[0] = true;
        }
        if (r == m - 1 || c == n - 1) {
            reaches[1] = true;
        }

        // Explore neighbors
        for (int i = 0; i < 4; i++) {
            int nr = r + dr[i];
            int nc = c + dc[i];
            
            if (nr >= 0 && nr < m && nc >= 0 && nc < n &&
                !visited[nr][nc] && heights[nr][nc] <= heights[r][c]) {
                dfs(nr, nc, visited, reaches);
            }
        }
    }
}
```
### Algorithm
- Initialize an empty list `result`.
- Iterate through each cell `(r, c)` in the `m x n` grid.
- For each cell, perform a Depth-First Search (DFS) to check if it can reach both oceans.
- The DFS needs to keep track of visited cells for the current starting cell to avoid infinite loops.
- The DFS also needs to track if a Pacific border (row 0 or col 0) and an Atlantic border (row `m-1` or col `n-1`) have been reached.
- The DFS can only move from a cell `(r1, c1)` to a neighbor `(r2, c2)` if `heights[r2][c2] <= heights[r1][c1]`.
- If the DFS from `(r, c)` confirms reachability to both oceans, add `[r, c]` to the `result` list.
- Return `result` after checking all cells.

## Multi-source Search (DFS/BFS) from Oceans
A much more efficient approach is to reverse the problem. Instead of checking where water can flow *to* from each cell, we find which cells can be reached by water flowing *from* the oceans. We can think of this as water flowing 'uphill' from the ocean shores. The cells that can be reached by both oceans are our answer.
**Time:** O(m*n). We run two separate multi-source DFS traversals. Each traversal visits each cell at most once. The first traversal for the Pacific costs O(m*n), and the second for the Atlantic costs O(m*n). The final iteration to find the intersection also costs O(m*n). The total time is linear with respect to the number of cells. · **Space:** O(m*n). We use two boolean matrices of size `m*n` to store reachability. The recursion stack for DFS can also reach a depth of O(m*n) in the worst case.
**Pros:** Highly efficient with linear time complexity.; Avoids all redundant computations by solving for all cells in just two main traversals.
**Cons:** Requires extra space for two `m x n` boolean matrices.; The logic is less direct and requires thinking about the problem in reverse, which can be less intuitive.
### Explanation
This method avoids redundant calculations by starting the search from the oceans and flowing inwards. We perform two separate multi-source traversals (using DFS or BFS).

1.  **Pacific Flow:** We identify all cells that can flow to the Pacific. We do this by starting a search from all cells on the Pacific border (row 0 and column 0) and finding all cells that can reach them. The condition for traversal is reversed: we can move from cell `A` to an adjacent cell `B` if `height(B) >= height(A)`. We use a `pacificReachable` boolean matrix to mark all such cells.

2.  **Atlantic Flow:** We do the same for the Atlantic Ocean. We start a search from all cells on the Atlantic border (last row and last column) and mark all reachable cells in an `atlanticReachable` matrix.

3.  **Result:** The final answer is the set of cells that are marked as reachable in *both* matrices. We can find this by iterating through the grid and collecting coordinates `(r, c)` where `pacificReachable[r][c]` and `atlanticReachable[r][c]` are both true.

```java
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> result = new ArrayList<>();
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return result;
        }

        int m = heights.length;
        int n = heights[0].length;

        boolean[][] pacificReachable = new boolean[m][n];
        boolean[][] atlanticReachable = new boolean[m][n];

        // Start DFS from all Pacific border cells
        for (int i = 0; i < m; i++) {
            dfs(i, 0, pacificReachable, Integer.MIN_VALUE, heights);
        }
        for (int j = 1; j < n; j++) {
            dfs(0, j, pacificReachable, Integer.MIN_VALUE, heights);
        }

        // Start DFS from all Atlantic border cells
        for (int i = 0; i < m; i++) {
            dfs(i, n - 1, atlanticReachable, Integer.MIN_VALUE, heights);
        }
        for (int j = 0; j < n - 1; j++) {
            dfs(m - 1, j, atlanticReachable, Integer.MIN_VALUE, heights);
        }

        // Find the intersection of the two sets of reachable cells
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        return result;
    }

    private void dfs(int r, int c, boolean[][] visited, int prevHeight, int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;

        if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || heights[r][c] < prevHeight) {
            return;
        }

        visited[r][c] = true;
        int currentHeight = heights[r][c];

        dfs(r + 1, c, visited, currentHeight, heights);
        dfs(r - 1, c, visited, currentHeight, heights);
        dfs(r, c + 1, visited, currentHeight, heights);
        dfs(r, c - 1, visited, currentHeight, heights);
    }
}
```
### Algorithm
- Initialize two boolean `m x n` matrices, `pacificReachable` and `atlanticReachable`, to `false`.
- Create a helper DFS function `dfs(r, c, visited, prevHeight)` that explores cells reachable by 'uphill' flow.
- **Pacific Search:** Start a DFS from every cell on the Pacific border (top and left edges). Mark all reachable cells in `pacificReachable` as `true`. The DFS can only move from cell `A` to cell `B` if `height(B) >= height(A)`.
- **Atlantic Search:** Similarly, start a DFS from every cell on the Atlantic border (bottom and right edges). Mark all reachable cells in `atlanticReachable` as `true`.
- **Find Intersection:** Iterate through the entire grid. If a cell `(r, c)` is `true` in both `pacificReachable` and `atlanticReachable`, add it to the final result list.
- Return the result list.

# Solutions
### Java

```java
class Solution { private int [][] heights ; private int m ; private int n ; public List < List < Integer >> pacificAtlantic ( int [][] heights ) { m = heights . length ; n = heights [ 0 ]. length ; this . heights = heights ; Deque < int []> q1 = new LinkedList <>(); Deque < int []> q2 = new LinkedList <>(); Set < Integer > vis1 = new HashSet <>(); Set < Integer > vis2 = new HashSet <>(); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( i == 0 || j == 0 ) { vis1 . add ( i * n + j ); q1 . offer ( new int [] { i , j }); } if ( i == m - 1 || j == n - 1 ) { vis2 . add ( i * n + j ); q2 . offer ( new int [] { i , j }); } } } bfs ( q1 , vis1 ); bfs ( q2 , vis2 ); List < List < Integer >> ans = new ArrayList <>(); for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int x = i * n + j ; if ( vis1 . contains ( x ) && vis2 . contains ( x )) { ans . add ( Arrays . asList ( i , j )); } } } return ans ; } private void bfs ( Deque < int []> q , Set < Integer > vis ) { int [] dirs = {- 1 , 0 , 1 , 0 , - 1 }; while (! q . isEmpty ()) { for ( int k = q . size (); k > 0 ; -- k ) { int [] p = q . poll (); for ( int i = 0 ; i < 4 ; ++ i ) { int x = p [ 0 ] + dirs [ i ]; int y = p [ 1 ] + dirs [ i + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n && ! vis . contains ( x * n + y ) && heights [ x ][ y ] >= heights [ p [ 0 ]][ p [ 1 ]]) { vis . add ( x * n + y ); q . offer ( new int [] { x , y }); } } } } } }
```

### CPP

```cpp
typedef pair < int , int > pii ; class Solution { public: vector < vector < int >> heights ; int m ; int n ; vector < vector < int >> pacificAtlantic ( vector < vector < int >>& heights ) { m = heights . size (); n = heights [ 0 ]. size (); this -> heights = heights ; queue < pii > q1 ; queue < pii > q2 ; unordered_set < int > vis1 ; unordered_set < int > vis2 ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { if ( i == 0 || j == 0 ) { vis1 . insert ( i * n + j ); q1 . emplace ( i , j ); } if ( i == m - 1 || j == n - 1 ) { vis2 . insert ( i * n + j ); q2 . emplace ( i , j ); } } } bfs ( q1 , vis1 ); bfs ( q2 , vis2 ); vector < vector < int >> ans ; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { int x = i * n + j ; if ( vis1 . count ( x ) && vis2 . count ( x )) { ans . push_back ({ i , j }); } } } return ans ; } void bfs ( queue < pii >& q , unordered_set < int >& vis ) { vector < int > dirs = { - 1 , 0 , 1 , 0 , - 1 }; while ( ! q . empty ()) { for ( int k = q . size (); k > 0 ; -- k ) { auto p = q . front (); q . pop (); for ( int i = 0 ; i < 4 ; ++ i ) { int x = p . first + dirs [ i ]; int y = p . second + dirs [ i + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n && ! vis . count ( x * n + y ) && heights [ x ][ y ] >= heights [ p . first ][ p . second ]) { vis . insert ( x * n + y ); q . emplace ( x , y ); } } } } } };
```

### Python

```python
class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: def bfs(q, vis): while q: for _ in range(len(q)): i, j = q . popleft() for a, b in [[0, - 1], [0, 1], [1, 0], [- 1, 0]]: x, y = i + a, j + b if (0 <= x < m and 0 <= y < n and (x, y) not in vis and heights[x][y] >= heights[i][j]): vis . add((x, y)) q . append((x, y)) m, n = len(heights), len(heights[0]) vis1, vis2 = set(), set() q1 = deque() q2 = deque() for i in range(m): for j in range(n): if i == 0 or j == 0: vis1 . add((i, j)) q1 . append((i, j)) if i == m - 1 or j == n - 1: vis2 . add((i, j)) q2 . append((i, j)) bfs(q1, vis1) bfs(q2, vis2) return [(i, j) for i in range(m) for j in range(n) if (i, j) in vis1 and (i, j) in vis2]

```