Solution: Pacific Atlantic Water Flow

Statement

Imagine an island with a rectangular shape that touches both the Pacific and Atlantic oceans. The northern and western sides meet the Pacific, while the southern and eastern sides touch the Atlantic. This island is divided into square cells.

To depict the height above sea level of each cell, we use an integer matrix, heights, of size $(m \times n)$. Here, heights[r][c] represents the elevation of the cell at coordinate $(r, c)$.

When heavy rain pours down on the island every few months, water flows from the island to both the Pacific and Atlantic oceans. The path of flow depends on the heights of the cells.

Consider a cell with a height of $9$ that’s higher than or equal to its neighboring cells to the north, east, west, and south. This indicates that water can flow from this cell to adjacent ones. Similarly, this process is repeated until the flow of water either reaches the Pacific or Atlantic border or a cell that can not flow water to any of its neighbors. If the flow of water starting from a cell can direct water to both the Pacific and Atlantic Ocean borders, we include it in the output.

Note: Any cell adjacent to an ocean can channel water into the ocean.

With this information, your task is to return a 2-D array of coordinates. Each entry $(r_i, c_i)$ in this array indicates that rainwater can flow from the cell at coordinate $(r_i, c_i)$ to both the Pacific and Atlantic oceans.

Constraints:

• $m ==$ heights.length

• $n ==$ heights[r].length, where $0 \leq r \leq m$

• $1 \leq m$, $n \leq 200$

• $0 \leq$ heights[r][c] $\leq 10^5$

Solution

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach

A naive approach to this problem involves performing depth-first search (DFS) from each cell in the matrix to determine whether it can flow water to both the Pacific and Atlantic oceans. It starts with the first cell in the matrix and performs DFS to find all the cells that can be reached from it. If the path of water can reach both the Pacific and Atlantic oceans, the cell is marked as a solution. Then, the algorithm repeats this process for each cell to find all cells that can flow water to both oceans.

The time complexity of this approach is $O(n^2 \times m^2)$ since, in the worst case, the entire matrix would be traversed for each cell.

The space complexity of this approach is $O(1)$ since a constant number of additional variables are used.

Optimized approach using Graphs

The idea stems from the observation that water flows downhill, seeking the lowest possible path. By starting the exploration from the ocean edges and traversing cells that are equal to or higher in elevation, we can identify regions where water can reach both the Pacific and Atlantic Oceans. The depth-first search (DFS) algorithm is chosen, since it naturally emulates the flow of water, exploring cells in a recursive manner and marking those that are reachable. The approach focuses on identifying cells that can be reached from both ocean edges, implying that water can flow in both directions and by finding the intersection of the sets of reachable cells from each ocean, the algorithm effectively pinpoints locations where water can flow to both oceans.

Here’s how the algorithm works:

• We initialize the following variables to assist us in performing DFS:

  • numRows: This is the total number of rows in the matrix.

  • numCols: This is the total number of columns in the matrix.

  • pacificReach: This is a hash set that will contain the coordinates of the cells that can be reached from the Pacific ocean.

  • atlanticReach: This is a hash set that will contain the coordinates of the cells that can be reached from the Atlantic ocean.

• The dfs function has the following parameters:

  • row, col: The coordinates of the initial cell where DFS will begin.

  • reach: The hash set of the respective ocean for which DFS is called.

• Here’s how the dfs function works:

  • The very first cell passed to the function will always be reachable since this cell is from the border of the matrix pertaining to the respective ocean. Therefore, the coordinates of this cell are added to reach.

  • For the cell above that has been added to reach, we perform DFS by exploring all four directions (top, bottom, left, right) from the cell. This is achieved through the use of a loop that adds the following coordinates to the current (row, col):

    • (1,0): The cell to the immediate top of the current cell is explored.

    • (0,1): The cell to the immediate bottom of the current cell is explored.

    • (-1,0): The cell to the immediate left of the current cell is explored.

    • (0,-1): The cell to the immediate right of the current cell is explored.

  • The following conditions are checked for each cell that is explored:

    • If the cell is out of bounds, it is skipped since it doesn’t exist in the matrix.

    • If the cell is already in reach, it is skipped since it has already been visited.

    • If the cell contains a height that is greater than the height of the previous cell, it is skipped since the previous cell can not be reached from this cell.

  • If the three conditions above are not satisfied, this means that the current cell is a valid cell on which we can continue DFS. So the dfs function is called again for this cell, where it is added to reach, and then its neighbors are explored again.

• The dfs function is then called for each cell of the Pacific and Atlantic border in the matrix, which populates pacificReach and atlanticReach with the coordinates of the cells that can flow water to the respective oceans.

• Finally, we determine the common coordinates in both pacificReach and atlanticReach and store them in the output array. These cells can flow water to both oceans, so we return the output array containing them.

The slides below illustrate how the algorithm runs: