Rain Reaching Both Seas

Medium

An island is split into cells, and elevation[r][c] is the height of the cell in row r, column c. One sea washes the top and left edges of the island, another washes the bottom and right edges. After rain, water flows from a cell into a side-adjacent cell if that cell is not higher. From any cell on an edge, water runs off into the sea along that edge. Return the coordinates [r, c] of every cell from which water can reach both seas, in any order.

Example 1

elevation=[[3, 3, 4], [2, 1, 5], [4, 6, 2]] → [[0, 2], [1, 2], [2, 0], [2, 1]]

For example, water on (0, 2) drains straight into the North Sea (top edge) and the Eastern Ocean (right edge), while (1, 1) at height 1 is stuck: every neighbour is higher. Cell (2, 0) touches both coasts by itself.

Example 2

elevation=[[5, 5], [5, 5]] → [[0, 0], [0, 1], [1, 0], [1, 1]]

Water also flows across flat ground, and every cell of a 2 × 2 island touches both coasts.

Example 3

elevation=[[7]] → [[0, 0]]

Constraints

1 ≤ number of rows, number of columns ≤ 200
0 ≤ elevation[r][c] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Array Matrix

Similar problems

Drain the Landlocked Ponds Medium Land Regions on a Map Medium Can the Ball Stop at the Target Medium Shortest Path of a Rolling Ball Medium Open a Minefield Cell Medium

Input

elevation=[[3, 3, 4], [2, 1, 5], [4, 6, 2]]

Expected

[[0, 2], [1, 2], [2, 0], [2, 1]]

Run checks the first 3 tests in your browser. Submit checks all 65 tests on the server, hidden ones included.