# Python solution with detailed explanation

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.