Concise Python version, same DFS idea


  • 0
    S
        def pacificAtlantic(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            if not matrix or len(matrix) == 0: return []
            m, n = len(matrix), len(matrix[0])
            pacific = [[False] * n for i in range(m)] #visited list
            atlantic = [[False] * n for i in range(m)] #visited list
            
            def dfs(i, j, prev, visited):
                if i < 0 or i >=m or j < 0 or j >= n or prev > matrix[i][j] or visited[i][j]:
                    return
                visited[i][j] = True
                for (d1,d2) in [(0,1), (1,0), (-1,0), (0,-1)]:
                    dfs(i+d1,j+d2, matrix[i][j], visited)
    
            for i in range(m):
                dfs(i, 0, float('-inf'), pacific)
                dfs(i, n-1, float('-inf'), atlantic)
            for j in range(n):
                dfs(0, j, float('-inf'), pacific)
                dfs(m-1, j, float('-inf'), atlantic)
                
            return [[i,j] for i in range(m) for j in range(n) if pacific[i][j] and atlantic[i][j]]
    

Log in to reply
 

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