LeetCode #417: Pacific Atlantic Water Flow

LeetCode Solutions

https://leetcode.com/problems/pacific-atlantic-water-flow/

This problem asks us to find the cells of a matrix where water can flow from Pacific Ocean to Atlantic Ocean, or vice versa. To solve this problem, we will perform a Depth-First Search (DFS) traversal of the matrix starting from the cells on the edges that border the Pacific Ocean and the Atlantic Ocean.

Here are the steps to solve the problem:

  1. Initialize two empty sets, pac and atl, to store the cells that can be reached from Pacific and Atlantic oceans, respectively.
  2. Define a DFS function, dfs, that takes four parameters:
    • r and c are the row and column indices of the current cell.
    • visit is a set that stores the visited cells.
    • prevHeight is the height of the previous cell in the DFS traversal.
  3. In the dfs function, if the current cell has not been visited and its height is greater than or equal to the height of the previous cell, add it to the visit set and recursively call dfs on its neighboring cells.
  4. Starting from the cells on the edges that border the Pacific Ocean, perform a DFS traversal and add the visited cells to the pac set.
  5. Starting from the cells on the edges that border the Atlantic Ocean, perform a DFS traversal and add the visited cells to the atl set.
  6. Iterate over all cells in the matrix and check if the cell is present in both pac and atl sets. If it is, add the cell’s indices to the result list.
  7. Return the result list.

Here’s the implementation of the solution:

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(heights), len(heights[0])
        pac, atl = set(), set()

        def dfs(r, c, visit, prevHeight):
            if not (r, c) in visit and 0 <= r < ROWS and 0 <= c < COLS and heights[r][c] >= prevHeight:
                visit.add((r, c))
                for row, col in [(r+1, c), (r-1, c), (r, c+1), (r, c-1)]:
                    dfs(row, col, visit, heights[r][c])
            
        for c in range(COLS):
            dfs(0, c, pac, heights[0][c])
            dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])

        for r in range(ROWS):
            dfs(r, 0, pac, heights[r][0])
            dfs(r, COLS - 1, atl, heights[r][COLS - 1])

        res = []
        for r in range(ROWS):
            for c in range(COLS):
                if (r, c) in pac and (r, c) in atl:
                    res.append([r, c])
        return res

Time and Space Complexity

The time complexity of this solution is O(mn) where m and n are the number of rows and columns in the matrix, respectively. We visit every cell of the matrix once during the DFS traversal.

The space complexity of this solution is also O(mn) where m and n are the number of rows and columns in the matrix, respectively. This is the space used to store the visit, pac, and atl sets.