python 189ms, but code not concise, need help


  • 0
    D

    Hi I am trying to do BFS for Pacific and Atlantic separately. Then look for the grids which can go both directions.
    The time complex looks ok, however I believe my code for sure could be optimized.

    Can someone help?

    Thanks

    def pacificAtlantic(self, matrix):
    """
    :type matrix: List[List[int]]
    :rtype: List[List[int]]
    """

        if not matrix or not matrix[0]: 
            return []
        m, n = len(matrix), len(matrix[0])
        res=[]
        Pdp = [[0] * n for i in range(m)]
        Pq=[]
        for i in range(m):
            for j in range(n):
                if i==0 or j==0:
                    Pdp[i][j] = 1
                    Pq.append((i,j))               
        Adp = [[0] * n for i in range(m)]
        Aq=[]
        for i in range(m):
            for j in range(n):
                if i==m-1 or j==n-1:
                    Adp[i][j] = 1
                    Aq.append((i,j))
                    
                    
        for i, j in Pq:
            for ni, nj in ((i, 1+j), (i, j-1), (i+1, j), (i-1, j)):
                if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] >= matrix[i][j] and Pdp[ni][nj]!=1:
                    Pdp[ni][nj] = 1
                    Pq.append((ni, nj))
                    
        for i, j in Aq:
            for ni, nj in ((i, 1+j), (i, j-1), (i+1, j), (i-1, j)):
                if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] >= matrix[i][j] and Adp[ni][nj]!=1:
                    Adp[ni][nj] = 1
                    Aq.append((ni, nj))
        
        for i in range(m):
            for j in range(n):
                if Pdp[i][j]+Adp[i][j]==2:
                    res.append([i,j])
        
        return res

Log in to reply
 

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