Python DFS 179ms

• Inspect flow from Pacific and Atlantic by DFS separately; keep exploring increasing path; Return points which are accessible by both Pacific and Atlantic DFS

``````    def pacificAtlantic(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
def helper(matrix, visited, row, col, x, y, flow):
visited[x][y] = True
flow[x][y] += 1
for i, j in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
if 0<=i<row and 0<=j<col and not visited[i][j] and matrix[x][y] <= matrix[i][j]:
helper(matrix, visited, row, col, i, j, flow)

if len(matrix)==0 or len(matrix[0])==0: return []
ret = []
row, col = len(matrix), len(matrix[0])
flow = [[0]*col for _ in xrange(row)]

# pacific
visited = [[False]*col for _ in xrange(row)]
for i in xrange(row):
if not visited[i][0]:
helper(matrix, visited, row, col, i, 0, flow)
for j in xrange(col):
if not visited[0][j]:
helper(matrix, visited, row, col, 0, j, flow)

# atlantic
visited = [[False]*col for _ in xrange(row)]
for i in xrange(row):
if not visited[i][col-1]:
helper(matrix, visited, row, col, i, col-1, flow)
for j in xrange(col):
if not visited[row-1][j]:
helper(matrix, visited, row, col, row-1, j, flow)

for i in xrange(row):
for j in xrange(col):
if flow[i][j] == 2:
ret.append([i, j])
return ret
``````

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