417. Pacific Atlantic Water Flow

Question: Pacific Atlantic Water Flow

Solution

想法：

檢視每一格，看那一格可不可以到 pacific 跟 atlanic，但這樣的時間複雜度會是 O((m * n )^2)

用另一個想法：

1. 先找出所有可以到 pacific 的格子，也就是從 Pacific 開始走：

   
   1. row = 0，c = 0, 1, 2, 3, 4，開始往內走
   2. columns = 0, row = 0, 1, 2, 3, 4 開始往內走。
   3. 走得到的座標 (r, c) 放入 pacific 的 set() 中

2. 同樣從 Atlantic 開始走：

   

   
   

   1. row = 4, c = 0, 1, 2, 3, 4
   2. column = 4, row = 0, 1, 2, 3, 4
   3. 走得到的座標 (r, c) 放入 atlantic 的 set() 中

3. 找 pacific 跟 atlantic 的交集

Time Complexity: O(m * n)

class Solution(object):

def pacificAtlantic(self, heights):

"""

:type heights: List[List[int]]

:rtype: List[List[int]]

"""

rows, columns = len(heights), len(heights[0])

pac, atl = set(), set()

res = list()

def dfs(r, c, visited, pre_height):

if (

r < 0 or

c < 0 or

r > rows - 1 or

c > columns - 1 or

(r, c) in visited or

heights[r][c] < pre_height

):

return

visited.add((r, c))

dfs(r - 1, c, visited, heights[r][c])

dfs(r + 1, c, visited, heights[r][c])

dfs(r, c - 1, visited, heights[r][c])

dfs(r, c + 1, visited, heights[r][c])

for c in range(columns):

dfs(0, c, pac, heights[0][c])

dfs(rows - 1, c, atl, heights[rows - 1][c])

for r in range(rows):

dfs(r, 0, pac, heights[r][0])

dfs(r, columns - 1, atl, heights[r][columns - 1])

for position in pac:

if position in atl:

res.append(list(position))

return res

Video Solution