Show problems as
Classic problem #417MediumArrayDepth-First SearchBreadth-First SearchMatrix

Pacific Atlantic Water Flow

Real-world version: Rooftop Twin Drainage
Tracked in this browser only
Read Pacific Atlantic Water Flow on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A flat roof is paved with square tiles laid out in a rows x cols grid. levels[r][c] is the height of the tile in row r, column c.

Rain that lands on a tile spreads to any tile sharing an edge with it whose height is the same or lower, and keeps spreading from there under the same rule. Two gutters collect the runoff:

  • the front gutter runs along the top row and the left column, so water standing on any tile of row 0 or column 0 is collected there;
  • the back gutter runs along the bottom row and the right column, so water standing on any tile of row rows - 1 or column cols - 1 is collected there.

A tile is twin-draining when rain landing on it can reach the front gutter and can also reach the back gutter. Return the coordinates [r, c] of every twin-draining tile. The coordinates may be listed in any order.

Examples

Example 1

Input
levels = [[4, 2, 7, 3], [3, 5, 6, 1], [8, 4, 2, 9], [2, 1, 3, 5]]
Output
[[0, 2], [0, 3], [1, 1], [1, 2], [2, 0], [3, 0]]

Tile [1, 1] stands at height 5. Water runs from it to [0, 1] at height 2, which lies in the top row and so reaches the front gutter, and it runs to [2, 1] and on to [3, 1], which lies in the bottom row and so reaches the back gutter.

Example 2

Input
levels = [[1, 5, 2], [4, 3, 6]]
Output
[[0, 1], [0, 2], [1, 0], [1, 2]]

Tile [1, 2] lies in the right column, and water runs from it to [0, 2] in the top row, so both gutters are reached. Tile [0, 0] lies in the top row, but both of its neighbours stand higher, so no water leaves it and the back gutter stays out of reach.

Example 3

Input
levels = [[9, 3, 9], [9, 3, 9], [9, 3, 9]]
Output
[[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]

From tile [1, 1] at height 3 the only tiles at the same height or lower are [0, 1] in the top row and [2, 1] in the bottom row, so both gutters are reached.

Example 4

Input
levels = [[7]]
Output
[[0, 0]]

The single tile lies in the top row and in the bottom row at once.

Constraints

  • rows == levels.length
  • cols == levels[r].length
  • 1 <= rows, cols <= 200
  • 0 <= levels[r][c] <= 10^5

The values you return may be in any order.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def pacific_atlantic(levels: list[list[int]]) -> list[list[int]]:
Java
public List<List<Integer>> pacificAtlantic(int[][] levels)

More on the same topics