Pacific Atlantic Water Flow

Medium

Pacific Atlantic Water Flow

Medium

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and what is the maximum possible size (rows and columns)?
Can the elevation values in the matrix be negative?
If a cell can reach both oceans, should I include it only once in the result?
Is the matrix guaranteed to be rectangular (i.e., all rows have the same number of columns)?
What should I return if the input matrix is empty (null or has zero rows/columns)?

Brute Force Solution

Approach

The problem asks us to find which locations in a grid can flow to both the Pacific and Atlantic oceans. A brute force approach involves checking every single location to see if it can reach both oceans.

Here's how the algorithm would work step-by-step:

For each location in the grid, imagine starting a journey from that location.
From that starting location, try going up, down, left, and right to neighboring locations, but only if the neighbor is not higher than your current location (water flows downhill or stays at the same level).
Keep exploring from each reachable location by following the same rule until you cannot go any further.
While exploring, check if you ever reach the edge of the grid that represents the Pacific ocean. If you do, mark that the starting location can reach the Pacific.
Also, check if you ever reach the edge of the grid that represents the Atlantic ocean. If you do, mark that the starting location can reach the Atlantic.
If, after exploring everywhere possible from a starting location, you find that it can reach both the Pacific and the Atlantic, then add that location to the answer.
Repeat this entire process (starting a journey and exploring) for every single location in the grid.

Code Implementation

def pacific_atlantic(heights):
    if not heights:
        return []

    number_of_rows = len(heights)
    number_of_columns = len(heights[0])
    reachable_pacific = set()
    reachable_atlantic = set()
    result = []

    def explore(row, column, reachable_set):
        # Add current cell to reachable set.
        reachable_set.add((row, column))

        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        for row_change, column_change in directions:
            new_row = row + row_change
            new_column = column + column_change

            # Check if valid neighbor
            if 0 <= new_row < number_of_rows and 0 <= new_column < number_of_columns \
                    and (new_row, new_column) not in reachable_set \
                    and heights[new_row][new_column] >= heights[row][column]:
                explore(new_row, new_column, reachable_set)

    # Explore from Pacific edge
    for row in range(number_of_rows):
        explore(row, 0, reachable_pacific)

    for column in range(number_of_columns):
        explore(0, column, reachable_pacific)

    # Explore from Atlantic edge
    for row in range(number_of_rows):
        explore(row, number_of_columns - 1, reachable_atlantic)

    for column in range(number_of_columns):
        explore(number_of_rows - 1, column, reachable_atlantic)

    # Find cells reachable from both
    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if (row, column) in reachable_pacific and (row, column) in reachable_atlantic:
                result.append([row, column])

    return result

Big(O) Analysis

Time Complexity

O(m*n*m*n) – The brute force solution iterates through each cell in the m x n grid, resulting in m*n starting points. From each starting point, a depth-first search (DFS) or breadth-first search (BFS) explores possible paths. In the worst case, the search from each cell might visit all other cells in the grid again (m*n). Therefore, the overall time complexity becomes O(m*n*m*n), where m and n are the dimensions of the grid.

Space Complexity

O(M * N) – The algorithm uses a Depth-First Search (DFS) to explore reachable locations from each cell in the grid. During the exploration from each starting location, we need to keep track of visited locations to avoid cycles. This is done implicitly through the recursion stack and also requires maintaining potentially two boolean matrices of size M x N to track which cells can reach the Pacific and Atlantic oceans respectively. Therefore, the auxiliary space used is proportional to the size of the input grid, resulting in a space complexity of O(M * N), where M is the number of rows and N is the number of columns in the grid.

Optimal Solution

Approach

The key idea is to start from the oceans and work our way inland. We use the property that water can only flow from higher or equal elevation to lower elevation to determine what cells can reach each ocean.

Here's how the algorithm would work step-by-step:

Imagine two separate teams of explorers, one starting from the Pacific Ocean coastline and the other from the Atlantic Ocean coastline.
Each explorer team can only move to adjacent land cells that are at the same height or higher than the cell they are currently on.
The Pacific team explores and marks all land cells reachable from the Pacific Ocean.
Independently, the Atlantic team explores and marks all land cells reachable from the Atlantic Ocean.
Finally, identify the land cells that both teams have marked. These are the cells that can reach both oceans.

Code Implementation

def pacific_atlantic(heights):
    if not heights:
        return []

    number_of_rows = len(heights)
    number_of_columns = len(heights[0])

    pacific_reachable = [[False] * number_of_columns for _ in range(number_of_rows)]
    atlantic_reachable = [[False] * number_of_columns for _ in range(number_of_rows)]

    def depth_first_search(row, column, reachable_matrix, previous_height):
        if row < 0 or row >= number_of_rows or column < 0 or column >= number_of_columns or \
           reachable_matrix[row][column] or heights[row][column] < previous_height:
            return

        reachable_matrix[row][column] = True

        # Explore adjacent cells with higher or equal height.
        depth_first_search(row + 1, column, reachable_matrix, heights[row][column])

        depth_first_search(row - 1, column, reachable_matrix, heights[row][column])

        depth_first_search(row, column + 1, reachable_matrix, heights[row][column])

        depth_first_search(row, column - 1, reachable_matrix, heights[row][column])

    # Start DFS from all border cells connected to the Pacific.
    for column_index in range(number_of_columns):
        depth_first_search(0, column_index, pacific_reachable, -1)

    for row_index in range(number_of_rows):
        depth_first_search(row_index, 0, pacific_reachable, -1)

    # Start DFS from all border cells connected to the Atlantic.
    for column_index in range(number_of_columns):
        depth_first_search(number_of_rows - 1, column_index, atlantic_reachable, -1)

    for row_index in range(number_of_rows):
        depth_first_search(row_index, number_of_columns - 1, atlantic_reachable, -1)

    result = []

    # Cells reachable from both oceans are added to the result.
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if pacific_reachable[row_index][column_index] and atlantic_reachable[row_index][column_index]:
                result.append([row_index, column_index])

    return result

Big(O) Analysis

Time Complexity

O(m*n) – We perform two separate Depth-First Searches (DFS) or Breadth-First Searches (BFS). The first explores cells reachable from the Pacific Ocean and the second explores cells reachable from the Atlantic Ocean. In the worst case, each cell in the m x n grid can be visited during each of these searches. Thus, the time complexity is proportional to the size of the grid, leading to O(m*n), where m is the number of rows and n is the number of columns. The final step to identify common cells reachable from both oceans takes O(m*n) time, but that doesn't change the overall asymptotic complexity.

Space Complexity

O(M * N) – The algorithm uses two boolean matrices, pacificReachable and atlanticReachable, to keep track of cells reachable from each ocean, where M is the number of rows and N is the number of columns in the input matrix. These matrices each have M * N elements, representing the visited status of each cell. Therefore, the auxiliary space used is proportional to the size of the input matrix. Thus the total space complexity is O(M * N).

Edge Cases

Case	How to Handle
Null or empty matrix	Return an empty list if the input matrix is null or has zero rows/columns to avoid null pointer exceptions and invalid calculations.
Matrix with a single row or column	The solution should correctly identify cells that flow to both oceans even with only one row or column.
Matrix with all identical values	All cells should be reachable from both oceans, leading to a result containing all cells.
Large matrix (potential stack overflow with recursion)	Use iterative depth-first search (DFS) or breadth-first search (BFS) instead of recursive DFS to avoid stack overflow errors for large inputs.
Matrix with integer overflow potential during calculations	The algorithm doesn't perform any arithmetic operations that could lead to an overflow, so this is not a concern.
Matrix with negative height values (invalid input)	Treat negative height values as an error or assume all values are non-negative based on problem constraints.
A matrix where no cell can reach both oceans	The algorithm should correctly return an empty list when no cell satisfies the condition.
Connectivity cycles that could cause infinite loops	The visited set prevents cycles during DFS/BFS by marking cells that are currently being explored.