# A reversed Python DFS solution using stack with explanation, beating 89%

• A point P should have the following two properties if it is included in the returned array:

1. There is an non-decreasing path from a coast point of Pacific to P.
2. There is an non-decreasing path from a coast point of Atlantic to P.

Here coast point means a point which is next to the oceans, which means the points in the first row and the first column are all coast points of Pacific, and the points in the last row and the last column are all coast points of Atlantic.

Therefore, we can compute the points that have the two properties respectively by running DFS / BFS twice, and return the points with both properties.

``````class Solution(object):
def pacificAtlantic(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
M = len(matrix)
if M == 0:
return []
N = len(matrix[0])
res = []
visitedPac = [[False] * N for _ in range(M)]
visitedAtl = [[False] * N for _ in range(M)]
stackPac = []
stackAtl = []
# init with coast points
for i in range(M):
visitedPac[i][0] = True
visitedAtl[i][N - 1] = True
stackPac.append((i, 0))
stackAtl.append((i, N - 1))
for j in range(N):
visitedPac[0][j] = True
visitedAtl[M - 1][j] = True
stackPac.append((0, j))
stackAtl.append((M - 1, j))
# dfs
self.dfs(matrix, M, N, stackPac, visitedPac)
self.dfs(matrix, M, N, stackAtl, visitedAtl)
# combine
for i in range(M):
for j in range(N):
if visitedPac[i][j] and visitedAtl[i][j]:
res.append([i, j])
return res

def dfs(self, matrix, M, N, stack, visited):
dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while stack:
pos = stack.pop()
for d in dirs:
i = pos[0] + d[0]
j = pos[1] + d[1]
if 0 <= i < M and 0 <= j < N and not visited[i][j] and matrix[i][j] >= matrix[pos[0]][pos[1]]:
visited[i][j] = True
stack.append((i, j))

``````

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