Pacific Atlantic Water Flow

 

1. Clarify the problem: Before diving into solving the problem, let's clarify the requirements:

  • We are given a matrix representing the heights of a grid of cells.
  • Water can flow from a cell to its neighboring cell if and only if the neighboring cell has a height greater than or equal to the current cell's height.
  • The Pacific Ocean is represented by the left and top borders of the matrix, and the Atlantic Ocean is represented by the right and bottom borders of the matrix.
  • We need to find the cells where water can flow from both the Pacific and Atlantic Oceans.

2. Analyze the problem: To solve this problem, we can use a depth-first search (DFS) approach.

  • We can perform two separate DFS traversals, starting from the Pacific and Atlantic Oceans, respectively.
  • We start by initializing two boolean matrices, one for the cells reachable from the Pacific Ocean and another for the cells reachable from the Atlantic Ocean.
  • We perform DFS from each ocean, visiting neighboring cells and marking them as reachable in the corresponding matrix.
  • After the DFS traversals, we iterate over all cells and find the cells that are reachable from both oceans.

3. Design an algorithm: Here is the algorithm to solve the problem:

  1. If the input matrix is empty, return an empty list.
  2. Initialize variables for the number of rows and columns of the matrix.
  3. Initialize two boolean matrices, one for the cells reachable from the Pacific Ocean and another for the cells reachable from the Atlantic Ocean. Both matrices should have the same size as the input matrix, and initially, all cells are marked as unreachable.
  4. Perform two separate DFS traversals, one starting from each ocean:
    • For each DFS traversal, create a stack to store the cells to be visited.
    • Push the border cells of the corresponding ocean into the stack.
    • While the stack is not empty:
      • Pop a cell from the stack.
      • Mark the cell as reachable in the corresponding boolean matrix.
      • For each neighboring cell that is not already marked as reachable and has a height greater than or equal to the current cell's height:
        • Push the neighboring cell into the stack.
  5. Iterate over all cells and find the cells that are reachable from both oceans.
  6. Return the list of coordinates of the reachable cells.

4. Explain your approach: The approach involves using DFS to traverse the matrix from both the Pacific and Atlantic Oceans. We create two boolean matrices to mark the cells that are reachable from each ocean. By performing separate DFS traversals, we mark the reachable cells. Finally, we iterate over all cells and find the cells that are reachable from both oceans.

5. Write clean and readable code:

python
def pacificAtlantic(matrix):
    if not matrix:
        return []

    rows, cols = len(matrix), len(matrix[0])
    pacific_reachable = [[False] * cols for _ in range(rows)]
    atlantic_reachable = [[False] * cols for _ in range(rows)]

    def dfs(row, col, reachable):
        reachable[row][col] = True
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        for dx, dy in directions:
            new_row, new_col = row + dx, col + dy
            if (
                0 <= new_row < rows
                and 0 <= new_col < cols
                and not reachable[new_row][new_col]
                and matrix[new_row][new_col] >= matrix[row][col]
            ):
                dfs(new_row, new_col, reachable)

    for row in range(rows):
        dfs(row, 0, pacific_reachable)
        dfs(row, cols - 1, atlantic_reachable)

    for col in range(cols):
        dfs(0, col, pacific_reachable)
        dfs(rows - 1, col, atlantic_reachable)

    reachable_cells = []
    for row in range(rows):
        for col in range(cols):
            if pacific_reachable[row][col] and atlantic_reachable[row][col]:
                reachable_cells.append([row, col])

    return reachable_cells

6. Test your code: We should test our code with different test cases to ensure its correctness and handle potential edge cases.

python
# Test case 1:
matrix1 = [
    [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]
]
print(pacificAtlantic(matrix1))
# Expected output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]

# Test case 2:
matrix2 = [
    [3, 3, 3, 3, 3],
    [3, 0, 3, 0, 3],
    [3, 3, 3, 3, 3]
]
print(pacificAtlantic(matrix2))
# Expected output: [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4], [1, 0], [1, 2], [1, 4], [2, 0], [2, 1], [2, 2], [2, 3], [2, 4]]

7. Optimize if necessary: The solution can be optimized further by using memoization to avoid redundant DFS calls. By memoizing the results of previous DFS calls, we can avoid revisiting cells that have already been marked as reachable. This optimization can improve the performance of the solution.

8. Handle error cases: The code assumes that the input matrix is valid and satisfies the problem constraints. If the matrix is empty or contains invalid values, the behavior of the code is undefined.

9. Discuss complexity analysis:

  • The time complexity of this solution is O(R * C), where R is the number of rows and C is the number of columns in the matrix. We perform two separate DFS traversals, each visiting each cell once.
  • The space complexity is O(R * C) as well, considering the space used by the two boolean matrices to store the reachable cells.
  • The solution has an optimal time and space complexity given the problem requirements.
Next Post Previous Post