**Solution**

**Pacific Atlantic Water Flow** https://leetcode.com/problems/pacific-atlantic-water-flow/

**Brute Force Solution**

- For every point in the grid, find whether it can reach both pacific and atlantic. You can use standard DFS or BFS for this. There are mn points and DFS/BFS is O(2mn).

**Optimized Solution**

- On the other hand, we can consider the flip side. We can let the pacific and atlantic ocean "flow into" the matrix as much as possible, using 2 boolean arrays, one for each ocean. The result are the points that are true in both boolean table.
- Two Queue and add all the Pacific border to one queue; Atlantic border to another queue.
- Keep a visited matrix for each queue. In the end, add the cell visited by two queue to the result.
- Water flows from ocean to the cell. Since water can only flow from high/equal cell to low cell,
**add the neighboor cell with height larger or equal to current cell to the queue and mark as visited**.

```
if 0<=x1<N and 0<=y1<M and not visited[x1][y1] and matrix[x1][y1] >= matrix[x][y]
```

- Note we can also use DFS here. Do a DFS from every pacific point and then from every atlantic point. Take an intersection later.
- https://discuss.leetcode.com/topic/62280/simple-commented-java-solution-with-thinking-progress-o-n
- https://discuss.leetcode.com/topic/62379/java-bfs-dfs-from-ocean

```
from Queue import Queue
class Solution(object):
def bfs(self, q, matrix, visited):
N, M = len(matrix), len(matrix[0])
while q.empty() == False:
(x,y) = q.get()
candidates = [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]
for (x1,y1) in candidates:
if 0<=x1<N and 0<=y1<M and not visited[x1][y1] and matrix[x1][y1] >= matrix[x][y]:
q.put((x1,y1))
visited[x1][y1]=True
return
def initialize_q(self, N, M, pac_q, atl_q, pac_visited, atl_visited):
for i in range(N):
pac_q.put((i,0))
atl_q.put((i, M-1))
pac_visited[i][0], atl_visited[i][M-1] = True, True
for j in range(M):
pac_q.put((0,j))
atl_q.put((N-1,j))
pac_visited[0][j], atl_visited[N-1][j] = True, True
return
def pacificAtlantic(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
if matrix == []:
return []
N, M = len(matrix), len(matrix[0])
pac_q, atl_q = Queue(), Queue()
pac_visited = [[False]*M for _ in range(N)]
atl_visited = [[False]*M for _ in range(N)]
self.initialize_q(N, M, pac_q, atl_q, pac_visited, atl_visited)
self.bfs(pac_q, matrix, pac_visited)
self.bfs(atl_q, matrix, atl_visited)
result = []
for i in range(N):
for j in range(M):
if pac_visited[i][j] and atl_visited[i][j]:
result.append([i,j])
return result
```