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

# 0417. Pacific Atlantic Water Flow

<https://leetcode.com/problems/pacific-atlantic-water-flow>

## Description

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]]
```

**Constraints:**

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

## ac1: DFS

reverse thinking

```java
class Solution {
    public List<int[]> pacificAtlantic(int[][] matrix) {
        List<int[]> res = new ArrayList<int[]>();
        // edge cases
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return res;
        }

        int row = matrix.length;
        int col = matrix[0].length;
        // two note matrix
        boolean[][] pacific = new boolean[row][col];
        boolean[][] atlantic = new boolean[row][col];

        // start from borders 
        int h = Integer.MIN_VALUE;
        for (int r = 0; r < row; r++) {
            dfs(matrix, pacific, r, 0, h);  
            dfs(matrix, atlantic, r, col-1, h);
        }
        for (int c = 0; c < col; c++) {
            dfs(matrix, pacific, 0, c, h);
            dfs(matrix, atlantic, row-1, c, h);
        }

        // get result
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    res.add(new int[]{r, c});
                }
            }
        }

        return res;
    }
    private void dfs(int[][] matrix, boolean[][] visited, int r, int c, int h) {
        if (r < 0 || r >= matrix.length || c < 0 || c >= matrix[0].length) return; // out of boundary
        if (visited[r][c]) return;  // visited before
        if (matrix[r][c] < h) return; // not qualified

        visited[r][c] = true;

        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        for (int[] d : dirs) {
            dfs(matrix, visited, r+d[0], c+d[1], matrix[r][c]);
        }
    }    
}

/*
two matrix: P A
start from border, DFS
*/
```