Find grid cells whose rainwater drains to both coasts
A hydrology team models a strip of land as a grid of elevations. The land runs between two coasts: the west coast borders the first column and the east coast borders the last column. The top and bottom edges are mountain walls, so no water leaves the grid there.
When rain falls on a cell, water can move to any neighbouring cell (up, down, left or right) whose height is less than or equal to the current cell’s height. Water in the first column can drain into the west coast, and water in the last column can drain into the east coast.
Implement findTwoCoastCells(heights). It returns every cell from which rainwater can reach both coasts.
findTwoCoastCells(heights) // => Array<[row, col]>
heights is a rectangular 2D array of numbers. heights[r][c] is the elevation of row r, column c.[]) or have empty rows ([[]]).[row, col] pairs, sorted by row and then by column.[] for an empty grid or when no cell qualifies. Do not mutate heights.findTwoCoastCells([
[1, 2, 2, 3],
[3, 4, 3, 2],
[2, 5, 1, 4],
]);
// => [[0, 3], [1, 1], [1, 2], [2, 1]]
// [2, 1] (height 5) drains west through [2, 0] and east through [1, 1], [1, 2], [1, 3].
findTwoCoastCells([[1, 2, 3]]);
// => [[0, 2]] 3 → 2 → 1 reaches the west; 3 is already on the east edge
findTwoCoastCells([[3, 1, 2]]);
// => [] the low middle cell traps water from both sides
findTwoCoastCells([[7], [2], [9]]);
// => [[0, 0], [1, 0], [2, 0]]
findTwoCoastCells([]);
// => []