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

# 417 Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note: The order of returned grid coordinates does not matter. Both m and n are less than 150. Example:

```
Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~ 
       ~  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  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).
```

**The Idea:** I first misinterpretted the problem. It was clarified when I thought about it the following way: imagine there is rain falling onto the grid, which coordinates on grid has their water flow to both the pacific and atlantic counter parts?

In summary, what we do is return the intersection of two depth first searches. We know that inorder for water to travel from both the pacific to atlantic, the dfs must begin along the coast of the respected edges of the grid. It then must 'travel' or traverse where ever it can. So define two dfs, the first along the coast the pacific and the other along the coast to the atlantic. When we travel, we inverse the rule, only go to areas that are higher than it. This works because it is the same thing as making the choice to start from the higher block, and then moving down to the lower block. Then the areas that were visited by both traversals are the solution.

![](/files/-LoJImwvcAn3rtx5wXEM)

**Complexity:** O(m*n*2) time and O(m*n*2) space

```python
def pacificAtlantic(self, matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[List[int]]
    """

    if not matrix: return []
    rows = len(matrix)
    cols = len(matrix[0])
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    visited_at = [[False for _ in row] for row in matrix]
    visited_pc = [[False for _ in row] for row in matrix]

    def not_overbound(row, col):
        return 0 <= row < rows and 0 <= col < cols

    def dfs(row, col, visited):
        visited[row][col] = True
        for direction in directions:
            next_r = row + direction[0]
            next_c = col + direction[1]
            if not_overbound(next_r, next_c) and not visited[next_r][next_c] \
                    and matrix[next_r][next_c] >= matrix[row][col]:
                dfs(next_r, next_c, visited)

    for row in range(0, rows):
        dfs(row, 0, visited_pc)         # pacific left
        dfs(row, cols - 1, visited_at)  # atlantic right
    for col in range(0, cols):
        dfs(0, col, visited_pc)         # pacific top
        dfs(rows - 1, col, visited_at)  # atlantic bottom

    both = []
    for row in range(0, rows):
        for col in range(0, cols):
            if visited_at[row][col] and visited_pc[row][col]:
                both.append([row, col])
    return both
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://maksimdan.gitbook.io/interview-practice-problems/leetcode_sessions/417-pacific-atlantic-water-flow.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.