Python DFS 179ms


  • 0
    X

    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
    

Log in to reply
 

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