# Python DFS

• I use two sets to keep track of cells that can be visited by each ocean, and take the intersection of the sets to find cells that can be reachable by both. The search starts at the 4 borders. Time complexity is O(n) since each cell is visited at most twice. Space used is O(n).

``````class Solution(object):
def dfs(self,i,j,matrix,explored,prev):
m,n = len(matrix),len(matrix[0])
if i < 0 or i >= m or j < 0 or j >= n or (i,j) in explored:
return
if matrix[i][j] < prev:
return
self.dfs(i-1,j,matrix,explored,matrix[i][j]) #up
self.dfs(i+1,j,matrix,explored,matrix[i][j]) #down
self.dfs(i,j-1,matrix,explored,matrix[i][j]) #left
self.dfs(i,j+1,matrix,explored,matrix[i][j]) #right

def pacificAtlantic(self, matrix):
if not matrix: return []
pacific,atlantic = set(),set()
m,n = len(matrix),len(matrix[0])
for i in xrange(n):
self.dfs(0,i,matrix,pacific,-1)
self.dfs(m-1,i,matrix,atlantic,-1)
for i in xrange(m):
self.dfs(i,0,matrix,pacific,-1)
self.dfs(i,n-1,matrix,atlantic,-1)
return list(pacific&atlantic)``````

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