leetcode-graph

417. Pacific Atlantic Water Flow.py

class Solution:
    """
    Thought Process: 
        grid coordinates --> It's definitely graph problem.
            -each cell(x,y) is node in the graph
            -it's directed edge, path exist only height of neighbor >= current of height(這裡很tricky, 周圍比較高, 所以水才可以留到current node)
                neighbor node -> current node
        
        DFS 
            Idea is we starting dfs on the border, exploring neighbor by neighbor. And, in the mean time, we use two hashset for two oceans to record if we can visited the ocean from the cell(x, y). For example,
            Initially
            p_visited = {} 
            a_visited = {}
            If (x,y) can reach pacific ocean, we add (x,y) into p_visited.
            Edge case:
                1.for the border on the left and top, they must be able to visited pacific ocean.
                1.for the border on the right and bottom, they must be able to visited atlantic ocean.
                
            After exploring, we iterate all cells, if cell(x,y) is both visited in p_visited and a_visited, we add into our ans list, because it mean this cell flow to both ocean.
            
        T: O(mn), two passes, because for dfs, each cell will be only visited once.
        S: O(mn), because we use extrac space p_visited and a_visited
    """
    directions = [(-1,0),(1,0),(0,1),(0,-1)]
    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
        
        def dfs(i, j, visited):
            if (i,j) in visited:
                return
            # cell (i, j) 是可以到某個海洋的
            visited.add((i,j))
            for directions in self.directions:
                next_i, next_j = i+directions[0], j+directions[1]
                # if height of neighbor >= current height, the neighbor node can flow into current node
                if 0<=next_i<m and 0<=next_j<n and matrix[next_i][next_j] >= matrix[i][j]:
                    dfs(next_i, next_j, visited)
                
        if not matrix:
            return []
        
        m = len(matrix)
        n = len(matrix[0])
        # store cell (x,y) that can reach to pacific ocean
        p_visited = set() 
        # store cell (x,y) that can reach to atlantic ocean
        a_visited = set()
        #step1: starting exploring from border
        for i in range(m):
            dfs(i, 0, p_visited)
            dfs(i, n-1, a_visited)
        for j in range(n):
            dfs(0, j, p_visited)
            dfs(m-1, j, a_visited) 
        print (p_visited)
        #step2: check if (x,y) can both reach to pacific and atlantic ocean
        ans = []
        for i in range(m):
            for j in range(n):
                if (i,j) in p_visited and (i,j) in a_visited:
                    ans.append([i,j])
        return ans