417. Pacific Atlantic Water Flow#

Difficulty: Medium

Link to Problem: To see the Pacific Atlantic Water Flow problem on LeetCode, click here!

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where \(result[i] = [r_i, c_i]\) denotes that rain water can flow from cell \((r_i, c_i)\) to both the Pacific and Atlantic oceans.

Constraints:

  • m == heights.length

  • n == heights[r].length

  • 1 <= m, n <= 200

  • 0 <= heights[r][c] <= \(10^5\)

Probelm Explanation:#

The problem at hand involves a scenario with a rectangular island surrounded by both the Pacific Ocean and the Atlantic Ocean. The Pacific Ocean is in contact with the island’s left and top edges, while the Atlantic Ocean is in contact with the island’s right and bottom edges. The goal is to determine which cells on the island can allow rainwater to flow to both the Pacific and Atlantic Oceans.

Here are the key details and constraints of the problem:

  1. The island is divided into a grid of square cells.

  2. Each cell is represented by an integer value in a matrix heights. The value at heights[r][c] represents the height above sea level of the cell at coordinates (r, c) on the island.

  3. Rainwater can flow from a cell to neighboring cells directly north, south, east, or west only if the neighboring cell’s height is less than or equal to the current cell’s height.

  4. Water can flow from any cell adjacent to the ocean into the ocean. This means water can flow from cells on the edge of the island to the Pacific Ocean and the Atlantic Ocean.

The task is to find and return a 2D list of grid coordinates where rainwater can flow from a cell to both the Pacific and Atlantic Oceans. In other words, you need to identify the cells that can send water to both the left and top edges (Pacific) and the right and bottom edges (Atlantic) of the island.

The problem is solved by performing a depth-first search (DFS) starting from the ocean edges and marking the cells that can flow to each ocean. Then, the algorithm identifies cells that are reachable from both oceans and returns their coordinates as the result.

The problem involves both traversal of the island and backtracking to find the solution, which makes it a classic graph traversal problem.

Solution:#

Here’s a Python function to implement this algorithm:

from typing import List

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        # Check if the input matrix is empty
        if not heights:
            return []
        
        m, n = len(heights), len(heights[0])
        
        # Initialize boolean matrices to keep track of cells reachable from each ocean
        pacific_reachable = [[False] * n for _ in range(m)]
        atlantic_reachable = [[False] * n for _ in range(m)]
        
        # Depth-First Search (DFS) function to mark cells that can be reached from an ocean
        def dfs(x, y, reachable):
            if reachable[x][y]:
                return
            reachable[x][y] = True
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                new_x, new_y = x + dx, y + dy
                if 0 <= new_x < m and 0 <= new_y < n and heights[new_x][new_y] >= heights[x][y]:
                    dfs(new_x, new_y, reachable)
        
        # Start DFS from the Pacific Ocean (left and top edges)
        for i in range(m):
            dfs(i, 0, pacific_reachable)
            dfs(i, n - 1, atlantic_reachable)
        
        for j in range(n):
            dfs(0, j, pacific_reachable)
            dfs(m - 1, j, atlantic_reachable)
        
        result = []
        
        # Find cells that can flow to both the Pacific and Atlantic oceans
        for i in range(m):
            for j in range(n):
                if pacific_reachable[i][j] and atlantic_reachable[i][j]:
                    result.append([i, j])
        
        return result

Explanation:#

The code defines a class called Solution with a method named pacificAtlantic. This method takes a 2D matrix heights, where each element represents the height above sea level of a cell on a rectangular island. The goal of the method is to find and return a list of grid coordinates (cells) from which rainwater can flow into both the Pacific and Atlantic Oceans.

The code uses a Depth-First Search (DFS) algorithm to traverse the island, starting from the ocean edges, and marks cells that are reachable from either the Pacific or Atlantic Ocean. It does this by creating two boolean matrices, pacific_reachable and atlantic_reachable, to keep track of cells that can be reached from each ocean.

The code iterates through the entire island, initiating DFS searches from the edges of the island. If a cell is reachable from an ocean (either Pacific or Atlantic), it is marked as reachable in the corresponding boolean matrix. The DFS function ensures that the traversal follows the rule that water can flow to a neighboring cell if the neighboring cell’s height is less than or equal to the current cell’s height.

After marking all reachable cells from both oceans, the code then looks for cells that are reachable from both the Pacific and Atlantic Oceans. If a cell satisfies this condition, it is added to the result list.

Finally, the code returns the result list, which contains the grid coordinates of cells from which rainwater can flow into both the Pacific and Atlantic Oceans.

The code provides a solution to the problem of finding cells on the island where water can reach both oceans, demonstrating a traversal algorithm that explores the connectivity of cells on the island.

Test cases:#

Here’s how you can use this solution:

# Example 1
heights1 = [
    [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]
]

solution = Solution()
print(solution.pacificAtlantic(heights1)) # Expected Output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]

# Example 2
heights2 = [[1]]
print(solution.pacificAtlantic(heights2)) # Expected Output: [[0, 0]]

[[0, 0]]

Time and Space Complexity Analysis#

Time Complexity: The time complexity of this solution is O(m * n), where ‘m’ is the number of rows in the input matrix and ‘n’ is the number of columns. Here’s a breakdown of the time complexity:

  1. Creating the pacific_reachable and atlantic_reachable matrices with dimensions m x n takes O(m * n) time.

  2. Initiating Depth-First Search (DFS) from the edges of the island takes O(m * n) time because it processes each cell once.

  3. The DFS function visits each cell at most once, and its time complexity is O(1) for each cell. The number of cells visited by the DFS in the worst case is m * n.

  4. The final step of identifying and appending cells to the result list takes O(m * n) time in the worst case.

Overall, the time complexity is dominated by the DFS and is O(m * n).

Space Complexity: The space complexity of this solution is also O(m * n). Here’s how the space is used:

  1. Two boolean matrices, pacific_reachable and atlantic_reachable, are created with dimensions m x n. Each matrix takes O(m * n) space, resulting in O(2 * m * n) space usage.

  2. The depth-first search (DFS) stack space during the recursive calls can go as deep as the diagonal of the grid, which is at most min(m, n). This additional space for the call stack is relatively small compared to the boolean matrices and can be considered O(min(m, n)).

  3. The result list stores the grid coordinates, and its size is determined by the number of cells that can flow to both oceans. In the worst case, this list can contain all m * n cells, so it takes O(m * n) space.

The overall space complexity is the sum of these components, which is O(m * n) + O(min(m, n)) + O(m * n). In big O notation, we can simplify this to O(m * n).

Challenging Exercises:#

  1. Optimization Challenge: Modify the algorithm to find the maximum flow of water from any cell to both the Pacific and Atlantic Oceans. In other words, find the cell(s) that can send the most water to both oceans.

  2. Efficiency Challenge: Optimize the time and space complexity of the algorithm while maintaining correctness. Aim to reduce both time and space complexity as much as possible.