📘

Pacific Atlantic Water Flow

Given an m x n matrix of heights, water flows from a cell to adjacent cells with height <= current height. The Pacific ocean touches the left and top edges. The Atlantic ocean touches the right and bottom edges.

Return cells where water can flow to both oceans. Output each cell as "row col" on a separate line, sorted by row then column.

Example:

Input:

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

Output:

Reasoning:

We start by identifying the Pacific and Atlantic ocean boundaries: the Pacific touches the left and top edges, and the Atlantic touches the right and bottom edges.
We then perform a depth-first search (DFS) from each ocean boundary to find the cells that can flow to each ocean, considering the height constraint: a cell can flow to an adjacent cell if the adjacent cell's height is $h_{adj} \leq h_{current}$ .
The DFS from the Pacific ocean boundary marks the cells that can flow to the Pacific, and the DFS from the Atlantic ocean boundary marks the cells that can flow to the Atlantic.
We find the intersection of the cells that can flow to both oceans and output them in the required format, sorted by row then column.

Constraints:

1 <= m, n <= 200
0 <= heights[i][j] <= 10^5

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘