Python fast BFS


  • 0
    Y

    Search from each ocean edge, exploring all higher or same height cells. Frontier holds all cells to be expanded.

    class Solution(object):
        def pacificAtlantic(self, matrix):
            if not matrix or not matrix[0]:
                return []
    
            rows, cols = len(matrix), len(matrix[0])
            atlantic, pacific = set(), set()        # cells that flow to each ocean
    
            for r in range(rows):
                atlantic.add((r, cols - 1))
                pacific.add((r, 0))
            for c in range(cols):
                atlantic.add((rows - 1, c))
                pacific.add((0, c))
    
            for ocean in [atlantic, pacific]:
    
                frontier = set(ocean)
                while frontier:
                    new_frontier = set()
                    for r, c in frontier:
                        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                            r1, c1 = r + dr, c + dc     # neighbouring cell
                            if r1 < 0 or r1 >= rows or c1 < 0 or c1 >= cols or (r1, c1) in ocean:
                                continue                # ignore already found or outside matrix
                            if matrix[r1][c1] >= matrix[r][c]:  # nbor flows to ocean
                                new_frontier.add((r1, c1))
                    frontier = new_frontier             # update frontier
                    ocean |= new_frontier               # add newly discovered to ocean
    
            return list(atlantic & pacific)             # set intersection

Log in to reply
 

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