417. Pacific Atlantic Water Flow

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        """ tc O(MN)  sc O(MN) M: rows N: cols
        where is Pacific rigion:  [0,x] or [y,0]
                 Atlantic region   [xx,n-1] or [m-1,yy]
        updating res condition: when start from (i,j) can go both pacific and atlantic region
        main idea: set global state variable a_seen and p_seen ( can be set or bucket list), start from         edges next to ocean (flood from the ocean)  do dfs(); in the end check coordinates wich both pass both oceans  
        
        1. initialize state set for both oceans 
        2. from four edges, do dfs to update ocean region status  
        3. return result 
        within dfs function:
            1. check if visited, and update seen 
            2. check unvisited neighbours, for those with [!!!!lower] value than current, proceed with next level recursion 
        """
        m,n = len(heights),len(heights[0])
        a_seen = set()
        p_seen = set()
        def dfs(i,j,seen):
            if (i,j) in seen:  # here can be ignored and add checker for new pos only since caller has verified (i,j) is not visited 
                return 
            seen.add((i,j))

            for dx,dy in ([1,0],[-1,0],[0,1],[0,-1]):
                new_i = i + dx
                new_j = j + dy
                # if nei can go to cur_pos, nei should have same flag status 
                #if x < 0 or y <0 or x >= rows or y >= cols or heights[x][y]< heights[i][j]:
                #  continue  will optimize
                if 0 <= new_i < m and 0 <= new_j < n and heights[i][j] <= heights[new_i][new_j]: # and (new_i,new_j) not in seen  
                    dfs(new_i,new_j,seen)
                    
        for row in range(m):
            dfs(row,0,p_seen)
            dfs(row,n-1,a_seen)
        for col in range(n):
            dfs(0,col,p_seen)
            dfs(m-1,col,a_seen)
            
        return list(a_seen&p_seen)