Python solution with detailed explanation


  • 0
    G

    Solution

    Pacific Atlantic Water Flow https://leetcode.com/problems/pacific-atlantic-water-flow/

    Brute Force Solution

    • For every point in the grid, find whether it can reach both pacific and atlantic. You can use standard DFS or BFS for this. There are mn points and DFS/BFS is O(2mn).

    Optimized Solution

    • On the other hand, we can consider the flip side. We can let the pacific and atlantic ocean "flow into" the matrix as much as possible, using 2 boolean arrays, one for each ocean. The result are the points that are true in both boolean table.
    • Two Queue and add all the Pacific border to one queue; Atlantic border to another queue.
    • Keep a visited matrix for each queue. In the end, add the cell visited by two queue to the result.
    • Water flows from ocean to the cell. Since water can only flow from high/equal cell to low cell, add the neighboor cell with height larger or equal to current cell to the queue and mark as visited.
    if 0<=x1<N and 0<=y1<M and not visited[x1][y1] and matrix[x1][y1] >= matrix[x][y]
    
    from Queue import Queue
    class Solution(object):
        def bfs(self, q, matrix, visited):
            N, M  = len(matrix), len(matrix[0])
            while q.empty() == False:
                (x,y) = q.get()
                candidates = [(x+1,y), (x-1,y), (x,y+1), (x,y-1)]
                for (x1,y1) in candidates:
                    if 0<=x1<N and 0<=y1<M and not visited[x1][y1] and matrix[x1][y1] >= matrix[x][y]:
                        q.put((x1,y1))
                        visited[x1][y1]=True
            return
        
        def initialize_q(self, N, M, pac_q, atl_q, pac_visited, atl_visited):
            for i in range(N):
                pac_q.put((i,0))
                atl_q.put((i, M-1))
                pac_visited[i][0], atl_visited[i][M-1] = True, True
                            
            for j in range(M):
                pac_q.put((0,j))
                atl_q.put((N-1,j))
                pac_visited[0][j], atl_visited[N-1][j] = True, True
            return
        
        def pacificAtlantic(self, matrix):
            """
            :type matrix: List[List[int]]
            :rtype: List[List[int]]
            """
            if matrix == []:
                return []
            N, M  = len(matrix), len(matrix[0])
            pac_q, atl_q = Queue(), Queue()
            pac_visited = [[False]*M for _ in range(N)]
            atl_visited = [[False]*M for _ in range(N)]        
            
            self.initialize_q(N, M, pac_q, atl_q, pac_visited, atl_visited)
            self.bfs(pac_q, matrix, pac_visited)            
            self.bfs(atl_q, matrix, atl_visited)            
            
            result = []
            for i in range(N):
                for j in range(M):
                    if pac_visited[i][j] and atl_visited[i][j]:
                        result.append([i,j])
                        
            return result
    

Log in to reply
 

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