12 lines simple BFS Python


  • 0

    Here I use a helper function check to process the BFS steps, and the initial conditions for our BFS are the outmost boundary of Pacific/Atlantic Ocean. Once we finished two BFS steps, get the intersection of two result sets and that's it.

    class Solution(object):
        def pacificAtlantic(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            def check(pos):
                res = set()
                while pos:
                    (i, j) = pos.pop()
                    res.add((i, j))
                    neighs = {(x,y) for x,y in ((i,j+1), (i,j-1), (i+1,j), (i-1,j)) \
                              if -1 < x < m and -1 < y < n and (x, y) not in res \
                              and matrix[x][y] >= matrix[i][j]}
                    pos |= neighs
                return res
                
            m, n = len(matrix), len(matrix[0]) if matrix else 0
            Pacific = {(i, 0) for i in range(m)} | {(0, j) for j in range(n)}
            Atlantic = {(i, n-1) for i in range(m)} | {(m-1, j) for j in range(n)}
            return map(list, check(Pacific) & check(Atlantic))
    

Log in to reply
 

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