Leetcode 417. Pacific Atlantic Water Flow

Problem

Leetcode 417 - Pacific Atlantic Water Flow

Example:

Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Approach

We can use DFS and using DP to track all the visited nodes and if both pacific and atlantic at its coordination is True, we return its coordinate

Here is the Python code for the solution:

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        pacific = [[False] * len(heights[0]) for _ in range(len(heights))]
        atlantic = [[False] * len(heights[0]) for _ in range(len(heights))]

        def dfs(i, j, visited):
            visited[i][j] = True
            for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
                ni, nj = i+dx, j+dy
                if 0 <= ni < len(heights) and 0 <= nj < len(heights[0]) and not visited[ni][nj]:
                    if heights[ni][nj] >= heights[i][j]:
                        dfs(ni, nj, visited)
        
        for i in range(len(heights)):
            dfs(i, 0, pacific)
        for j in range(len(heights[0])):
            dfs(0, j, pacific)
        
        for i in range(len(heights)):
            dfs(i, len(heights[0])-1, atlantic)
        for j in range(len(heights[0])):
            dfs(len(heights)-1, j, atlantic)

        res = []

        for i in range(len(heights)):
            for j in range(len(heights[0])):
                if pacific[i][j] and atlantic[i][j]:
                    res.append([i,j])
        
        print(pacific)
        print(atlantic)
        return res

Time Complexity and Space Complexity

Time Complexity: $O(n*m)$

Space Complexity: $O(n*m)$