
### Problem Statement

###### 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] = [r&#7522;, c&#7522;] denotes that rain water can flow from cell (r&#7522;, c&#7522;) to both the Pacific and Atlantic oceans.

![Pacific Atlantic](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] ]**

**Steps To Solve**

- Think of solution without code

  - Here we need to find the island cells from which water flows towards both the Pacific and Atlantic Ocean.
  - Water can flow in four directions from a cell if the height of the surrounding cell is same or lower than height of the current cell.
  - One possible solution to this is to take each cell and run dfs and find out if water flows in both the oceans.But it is time consuming O(M\*N)&sup2;.
  - To optimize our solution we start from the edge and then converge inside keeping visited arrays of island cells.
  - We will keep two arrays one for cells from where water can flow to pacific and another for cells from where water can flow to atlantic and then finally merge them.

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

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

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

```js
/**
 * @param {number[][]} heights
 * @return {number[][]}
 */
var pacificAtlantic = function (heights) {
  const n = heights.length;
  const m = heights[0].length;
  const dir = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  let res = [];
  if (n === 0) return res;
  const pacific = Array(n)
    .fill(null)
    .map((r) => Array(m).fill(false));
  const atlantic = Array(n)
    .fill(null)
    .map((r) => Array(m).fill(false));

  for (let i = 0; i < n; i++) {
    dfs(heights, pacific, Number.NEGATIVE_INFINITY, i, 0);
    dfs(heights, atlantic, Number.NEGATIVE_INFINITY, i, m - 1);
  }

  for (let i = 0; i < m; i++) {
    dfs(heights, pacific, Number.NEGATIVE_INFINITY, 0, i);
    dfs(heights, atlantic, Number.NEGATIVE_INFINITY, n - 1, i);
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (pacific[i][j] && atlantic[i][j]) {
        res.push([i, j]);
      }
    }
  }

  function dfs(heights, visited, prevHeight, x, y) {
    if (
      x < 0 ||
      x >= n ||
      y < 0 ||
      y >= m ||
      visited[x][y] ||
      heights[x][y] < prevHeight
    )
      return;
    visited[x][y] = true;

    for (let [i, j] of dir) {
      dfs(heights, visited, heights[x][y], x + i, y + j);
    }
  }

  return res;
};
```

###### Time and Space Complexity

- Time Complexity is **O(M\*N)**, in worst case, all cells are reachable to both oceans and would be visited twice. This case can occur when all elements are equal.
- Space complexity in this case is **O(M\*N)**, to mark the atlantic and pacific visited cells..
