Simple and Elegant Python DFS solution


  • 1

    Simply do two DFS, each time starting from the edges that belong to the Pacific and Atlantic Ocean.

    nodes = set(coords[type]) | set(zip(*coords)[type]) is a really neat trick to get the cells for each ocean. When type is 0, you will get the Pacific Ocean cells, when type is -1, you will get the Atlantic Ocean cells.

    The rest is standard DFS code already presented multiple times by others.

    class Solution(object):
        def pacificAtlantic(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            if not len(matrix) or not len(matrix[0]):
                return []
            rows, cols = len(matrix), len(matrix[0])
            coords = [[(row, col) for col in range(cols)] for row in range(rows)]
            def ocean_nodes(type):
                nodes = set(coords[type]) | set(zip(*coords)[type])
                traversable = set()
                def traverse(node):
                    if node in traversable:
                        return
                    traversable.add(node)
                    curr_height = matrix[node[0]][node[1]]
                    for direction in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                        row, col = node[0] + direction[0], node[1] + direction[1]
                        if 0 <= row < rows and 0 <= col < cols and curr_height <= matrix[row][col]:
                            traverse((row, col))
                [traverse(node) for node in nodes]
                return traversable
            return list(ocean_nodes(0) & ocean_nodes(-1))          
    

Log in to reply
 

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