> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/graph/35.-pacific-atlantic-water-flow.md).

# 35. 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.

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.leetcode.com/uploads/2021/06/08/waterflow-grid.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]]
```

**Example 2:**

```
Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]
```

## Solution:(DFS)

**Approach:**\
Now, if we start from the cells connected to atlantic ocean and visit all cells having height greater than current cell (**water can only flow from a cell to another one with height equal or lower**), we are able to reach some subset of cells (let's call them **`A`**).

![](https://assets.leetcode.com/users/images/7fe6657a-4bc1-4d68-8a26-befe6e106371_1616674367.2859244.png)

Next, we start from the cells connected to pacific ocean and repeat the same process, we find another subset (let's call this one **`B`**).

![](https://assets.leetcode.com/users/images/ef3a788b-7b66-4c70-a47c-58490b998177_1616674843.2320118.png)

The final answer we get will be the intersection of sets `A` and `B` (**`A ∩ B`**).

![](https://assets.leetcode.com/users/images/6a9f7a1f-105e-4d6c-8e7c-ede3a2f9b6de_1616674967.7329113.png)

```cpp
class Solution
{
public:
    void dfs(vector<vector<int>> &heights, vector<vector<bool>> &vs, int i, int j, int n, int m)
    {
        if (vs[i][j])
        {
            return;
        }
        
        vs[i][j] = true;

        if (i + 1 < n && heights[i + 1][j] >= heights[i][j])
        {
            dfs(heights, vs, i + 1, j, n, m);
        }

        if (j + 1 < m && heights[i][j + 1] >= heights[i][j])
        {
            dfs(heights, vs, i, j + 1, n, m);
        }

        if (i - 1 >= 0 && heights[i - 1][j] >= heights[i][j])
        {
            dfs(heights, vs, i - 1, j, n, m);
        }

        if (j - 1 >= 0 && heights[i][j - 1] >= heights[i][j])
        {
            dfs(heights, vs, i, j - 1, n, m);
        }

        return;
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights)
    {

        int n = heights.size();
        int m = heights[0].size();

        vector<vector<bool>> a(n, vector<bool>(m, false));
        vector<vector<bool>> p(n, vector<bool>(m, false));

        for (int i = 0; i < n; i++)
        {
            dfs(heights, p, i, 0, n, m);
            dfs(heights, a, i, m - 1, n, m);
        }

        for (int i = 0; i < m; i++)
        {
            dfs(heights, p, 0, i, n, m);
            dfs(heights, a, n - 1, i, n, m);
        }

        vector<vector<int>> res;

        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (a[i][j] && p[i][j])
                {
                    res.push_back({i, j});
                }
            }
        }

        return res;
    }
};
```

**Time Complexity : O(M \* N)**