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).
- 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.
from Queue import Queue class Solution(object): def bfs(self, q, matrix, visited): N, M = len(matrix), len(matrix) 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], 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[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) 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