A LeetCode Daily Series — Day 85

Today’s problem is called "Pacific Atlantic Water Flow"

Updated: at 07:00 AM

In this article, we will try to solve the “Pacific Atlantic Water Flow” problem efficiently using Depth-First Search (DFS). This problem is an interesting challenge that involves understanding grid traversal and water flow dynamics. Let’s dive into the problem, understand the intricacies, and see how we can approach it in an optimal way.

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

Cover Image

Understanding the Problem

Imagine a rectangular island represented by an m x n grid. Each cell in this grid has a certain height above sea level. The Pacific Ocean borders the island’s left and top edges, while the Atlantic Ocean borders the island’s right and bottom edges.

When it rains, water can flow from a cell to its neighboring cells if the neighboring cell’s height is less than or equal to the current cell’s height. Our task is to find all the cells from which water can flow to both the Pacific and Atlantic oceans.

Example 1

Consider the following grid:

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]]

For instance, water can flow from cell (0, 4) to both oceans:

The output for this grid would be the list of coordinates from which water can flow to both oceans: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]].

Example 2

Consider a single cell grid:

heights = [[1]]

In this case, the water can flow from the only cell (0, 0) to both oceans, so the output is [[0, 0]].

Using Efficient Approach: Depth-First Search (DFS)

Depth-First Search (DFS) is a powerful graph traversal technique that explores all possible paths from a given starting point by diving deep into each branch before backtracking. In this problem, we will use DFS to explore cells that can reach both the Pacific and Atlantic oceans.

We will perform the following steps:

  1. Use DFS to explore all cells that can reach the Pacific Ocean starting from the top and left edges.
  2. Use DFS to explore all cells that can reach the Atlantic Ocean starting from the bottom and right edges.
  3. Identify the cells that are common in both explorations.
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
    # Dimensions of the grid
    ROWS, COLS = len(heights), len(heights[0])

    # Sets to keep track of cells that can reach Pacific and Atlantic Oceans
    pac, atl = set(), set()

    # Depth-First Search (DFS) function
    def dfs(r, c, visit, prevHeight):
        # If the cell is out of bounds or has already been visited, return
        if (
            (r, c) in visit
            or r < 0
            or c < 0
            or r >= ROWS
            or c >= COLS
            or heights[r][c] < prevHeight
        ):
            return

        # Add the cell to the visited set
        visit.add((r, c))

        # Explore the neighboring cells
        dfs(r + 1, c, visit, heights[r][c])
        dfs(r - 1, c, visit, heights[r][c])
        dfs(r, c + 1, visit, heights[r][c])
        dfs(r, c - 1, visit, heights[r][c])

    # Perform DFS for each cell in the top and bottom rows for the Pacific and Atlantic Oceans respectively
    for c in range(COLS):
        dfs(0, c, pac, heights[0][c])        # Top row for Pacific
        dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])  # Bottom row for Atlantic

    # Perform DFS for each cell in the left and right columns for the Pacific and Atlantic Oceans respectively
    for r in range(ROWS):
        dfs(r, 0, pac, heights[r][0])        # Left column for Pacific
        dfs(r, COLS - 1, atl, heights[r][COLS - 1])  # Right column for Atlantic

    # Find cells that can reach both oceans
    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

Explanation

  1. Initialization:
    • We start by defining the dimensions of the grid ROWS and COLS.
    • Two sets, pac and atl, are initialized to keep track of cells that can reach the Pacific and Atlantic oceans, respectively.
  2. DFS Function:
    • The dfs function is designed to traverse the grid. It takes the current row r, column c, the set visit (either pac or atl), and the previous cell’s height prevHeight.
    • If the current cell is out of bounds, has already been visited, or its height is less than the previous cell’s height, we return from the function.
    • Otherwise, we add the current cell to the visit set and recursively call dfs for all neighboring cells (up, down, left, right).
  3. Pacific and Atlantic Edges:
    • We initiate DFS from all cells adjacent to the Pacific Ocean (left and top edges) and Atlantic Ocean (right and bottom edges).
  4. Result Compilation:
    • After performing DFS from all required cells, we iterate through the grid to find cells present in both pac and atl, adding them to the result list.

Time Complexity: O(m x n), where m is the number of rows and n is the number of columns. Each cell is processed a constant number of times.

Space Complexity: O(m x n) for the DFS stack and the sets storing visited cells.

DFS Result

Challenge for Adventurers!

Now that you’ve seen an efficient solution using DFS, try to think of other ways to solve this problem. Can you come up with a Breadth-First Search (BFS) solution or any other innovative approach? Dive deep into the problem, explore different algorithms, and enhance your problem-solving skills.

Conclusion

The “Pacific Atlantic Water Flow” problem is a great example of how graph traversal techniques like DFS can be used to solve complex grid-based problems efficiently. By understanding the problem requirements and carefully implementing the DFS approach, we can achieve an optimal solution.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series