Loading problem...
You are given a terrain map of a rectangular landmass represented as an m x n grid of elevation values. This landmass is uniquely positioned between two distinct bodies of water: the Northern Sea borders the top and left edges of the landmass, while the Southern Sea borders the bottom and right edges.
When rainfall occurs on any cell in the terrain, water naturally drains downhill toward adjacent cells. Specifically, water from a cell can flow to any of its four neighboring cells (north, south, east, or west) if the neighboring cell's elevation is less than or equal to the current cell's elevation. Water that reaches any cell adjacent to a sea naturally flows into that sea.
Your task is to identify all cells in the terrain from which rainwater can successfully drain into both the Northern Sea and the Southern Sea. These are the "dual drainage" cells — positions where water has viable paths flowing to both bodies of water.
Return a list of all such cell coordinates [row, column] where water can reach both seas. The order of cells in the result does not matter.
heights = [[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]][[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]These seven cells have drainage paths to both seas. For example, cell [2,2] with elevation 5 can drain north through [1,2]→[0,2] to the Northern Sea, and can drain east through [2,3]→[2,4] to the Southern Sea. Cell [4,0] directly borders both seas (left edge for Northern, bottom edge for Southern), making it an automatic dual-drainage cell.
heights = [[1]][[0,0]]With only one cell in the terrain, it borders all four edges simultaneously, meaning water can drain to both the Northern Sea and Southern Sea directly.
heights = [[1,2],[3,4]][[0,1],[1,0],[1,1]]In this 2x2 grid, cell [0,1] borders the Northern Sea (top edge) and can drain to [1,1]→Southern Sea. Cell [1,0] borders the Northern Sea (left edge) and Southern Sea (bottom edge). Cell [1,1] can drain through [0,1] to Northern Sea and directly borders the Southern Sea via bottom-right corner.
Constraints