Pacific Atlantic Water Flow

Description

There is an m x n rectangular island that borders both the Pacific and the Atlantic oceans. The island is partitioned into a grid of square cells.

The island receives a lot of rain, and the rainwater 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.

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), we need to return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rainwater can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

Let’s review an example below:

Coding exercise

Solution

The naive brute force approach would be to iterate over all the cells of the matrix and try to find the cells that manage to reach both oceans. For obvious reasons, this approach is slow and repeats a lot of the computations.

A more intuitive approach would be to start at the oceans and work our way up to the cells instead of searching for a path from every cell to the ocean. When we start from the ocean and work back to the cells, we can ensure that every visited cell must be connected to that ocean.

If we start traversing from the ocean and flip the condition (check for higher height instead of lower height), we know that every cell we visit can flow into that ocean during the traversal. We can start a traversal from every cell immediately beside the Pacific ocean and figure out what cells can flow into the Pacific. Similarly, we can do the same for the Atlantic ocean. In the end, the cells that end up connected to both oceans will be our ...