Two Drainage Basins
MediumGraphs
Problem
A hydrologist models a plateau as a height map heights. The North Lake borders the top row and the left column; the South Lake borders the bottom row and the right column.
Rain falling on a cell can flow to a horizontally or vertically adjacent cell whose height is less than or equal to the current one, and from any border cell straight into the lake(s) it borders.
Return the coordinates [r, c] of every cell whose rain can reach both lakes, sorted by row and then by column.
Example 1
- Input:
- heights = [[1,2,3],[8,9,4],[7,6,5]]
- Output:
- [[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
(0,0) and (0,1) are lower than every neighbour leading south or east, so their water only reaches the North Lake. Every other cell can reach both.
Example 2
- Input:
- heights = [[5]]
- Output:
- [[0,0]]
A single cell borders both lakes.
Constraints
- 1 ≤ rows, cols ≤ 200
- 0 ≤ heights[r][c] ≤ 10^5
Hint
Show the first hint
Simulating rain from every cell repeats the same downhill searches over and over.
Walkthrough
How to approach it
01Clarify before coding
- Can water flow between equal heights? Yes, to any neighbour with height ≤ current.
- Which borders feed which lake? Top row and left column → North; bottom row and right column → South. Corners may feed both.
- In what order should I return cells? Row-major: by row, then by column.
02Brute force
From every cell, run a DFS downhill and record whether it reaches each lake.
Cost: O((r · c)²): each of the r · c searches can explore the whole map, 1.6 · 10^9 operations for 200 × 200.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.