Pacific Atlantic Water Flow

To solve this coding challenge, we need to determine which grid cells in a
heights
matrix can flow into both the Pacific and Atlantic oceans. The Pacific Ocean touches the left and top edges, while the Atlantic Ocean touches the right and bottom edges of the matrix. Water can flow to neighboring cells only if the neighboring cells' height is less than or equal to the current cells' height.

Explanation

  1. Initialization : We initialize two boolean matrices,
    pacificReachable
    and
    atlanticReachable
    , to keep track of cells that can reach the Pacific and Atlantic oceans respectively.
  2. Depth-First Search (DFS) : We will perform DFS from all boundary cells of the matrix, marking cells in the
    pacificReachable
    matrix if starting from the Pacific boundary cells (top row and left column) and marking cells in the
    atlanticReachable
    matrix if starting from the Atlantic boundary cells (bottom row and right column).
  3. DFS Helper Function : Define a recursive DFS helper function that:
    • Marks the current cell as reachable.
    • Recursively visits all four possible directions (north, south, east, and west) if they haven't been visited yet and if the height of the neighboring cell is greater than or equal to the current cell's height.
  4. Boundary Traversal : Traverse all the boundary cells to initiate the DFS for both oceans. For the Pacific Ocean, traverse cells in the first row and first column. For the Atlantic Ocean, traverse cells in the last row and last column.
  5. Result Compilation : Traverse the entire matrix and collect cells that can reach both oceans (where both
    pacificReachable
    and
    atlanticReachable
    have
    True
    ).

    6. Step-by-Step Explanation/Detailed Steps in Pseudocode

  6. Initialize Constants and Matrices :
    • Get the number of rows (
      m
      ) and columns (
      n
      ) of the
      heights
      matrix.
    • Initialize two boolean matrices
      pacificReachable
      and
      atlanticReachable
      of the same size as the
      heights
      matrix and fill them with
      False
      .
  7. Define the DFS Function :
    • Implement a
      DFS
      function that takes parameters: matrix, current cell coordinates, previous cell height, and the reachability matrix (
      oceanReachable
      ).
    • The function should check boundaries and conditions to continue DFS.
    • Mark the cell as reachable.
    • Recursively call DFS for all four directions: up, down, left, right, if the conditions are satisfied.
  8. Run DFS from Pacific and Atlantic Boundaries :
    • For all cells in the first row and first column, initiate DFS for the Pacific Ocean reachability.
    • For all cells in the last row and last column, initiate DFS for the Atlantic Ocean reachability.
  9. Collect Result :
    • Traverse through each cell of the matrix and check if both
      pacificReachable
      and
      atlanticReachable
      are
      True
      .
    • Collect such cells into the result list.

Pseudocode

                                            
# Initialize environment
function pacificAtlantic(heights):
    rows = heights.length
    columns = heights[0].length
    
    # Create reachability matrices
    pacificReachable = createMatrix(rows, columns, False)
    atlanticReachable = createMatrix(rows, columns, False)

    # Define the DFS helper function
    function DFS(heights, row, col, prevHeight, reachableMatrix):
        if row < 0 or col < 0 or row >= rows or col >= columns:
            return
        if heights[row][col] < prevHeight or reachableMatrix[row][col]:
            return
        
        # Mark the cell as reachable
        reachableMatrix[row][col] = True
        
        # Visit all possible directions: north, south, east, west
        DFS(heights, row + 1, col, heights[row][col], reachableMatrix)
        DFS(heights, row - 1, col, heights[row][col], reachableMatrix)
        DFS(heights, row, col + 1, heights[row][col], reachableMatrix)
        DFS(heights, row, col - 1, heights[row][col], reachableMatrix)
    
    # Traverse boundaries for Pacific DFS
    for row in range(rows):
        DFS(heights, row, 0, -Infinity, pacificReachable)
        DFS(heights, row, columns - 1, -Infinity, atlanticReachable)
    
    for col in range(columns):
        DFS(heights, 0, col, -Infinity, pacificReachable)
        DFS(heights, rows - 1, col, -Infinity, atlanticReachable)
    
    # Collect results
    result = []
    for row in range(rows):
        for col in range(columns):
            if pacificReachable[row][col] and atlanticReachable[row][col]:
                result.append([row, col])
    
    return result

# This helper function creates a matrix with default value
function createMatrix(rows, columns, defaultValue):
    matrix = []
    for _ in range(rows):
        row = []
        for _ in range(columns):
            row.append(defaultValue)
        matrix.append(row)
    return matrix
By following this detailed explanation and given pseudocode, you should be able to solve the Pacific Atlantic Water Flow problem efficiently. The DFS ensures that we can explore all reachable cells from the boundaries, and the nested loops ensure that we correctly compile the final list of cells meeting the condition.