Cells Draining to Both Coasts
Problem
A height map of an island is a grid of numbers. The west coast runs along the top and left edges, and the east coast runs along the bottom and right edges. Rain on a cell flows to any sideways neighbour whose height is less than or equal to the cell's own height, and a cell on an edge drains straight into that coast. Return every cell, as [row, col] in row-major order, from which rain can reach both coasts. The grid has between 1 and 200 rows and columns, so running a separate search from every cell is too slow.
Examples
Input: 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]]
Output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]Input: heights = [[1, 2], [4, 3]]
Output: [[0, 1], [1, 0], [1, 1]]
Why: the corner holding 1 is lower than both of its neighbours, so it only reaches the west coastInput: heights = [[1]]
Output: [[0, 0]]
Why: edge case, a single cell touches both coastsHints
0 / 3
Searching downhill from each cell repeats the same work many times. Ask the question the other way round: which cells can each coast be reached from?
Start at every cell on one coast and walk uphill, moving to a neighbour only if it is at least as high as the current cell. Every cell you reach can drain back down to that coast.
Run that uphill flood fill once from the west edges and once from the east edges, then return the cells found by both, sorted by row and column.
Solution
Water flows from a cell to a neighbour that is no higher, so reversing the direction turns the question into a reachability search: starting from a coast, climb to any neighbour at least as high as where you stand. Every cell that climb reaches has a downhill path back to that coast. One flood fill seeded with all west-edge cells and one seeded with all east-edge cells each visit every cell at most once, and the answer is the intersection of the two visited sets. Time and space are both O(rows × cols).
def both_coasts(heights):
rows, cols = len(heights), len(heights[0])
def climb(starts): # every cell that drains to these edges
seen, stack = set(starts), list(starts)
while stack:
r, c = stack.pop()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if (0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen
and heights[nr][nc] >= heights[r][c]): # walk uphill only
seen.add((nr, nc))
stack.append((nr, nc))
return seen
west = climb([(r, 0) for r in range(rows)] + [(0, c) for c in range(cols)])
east = climb([(r, cols - 1) for r in range(rows)] + [(rows - 1, c) for c in range(cols)])
return sorted([r, c] for r, c in west & east)
print(both_coasts([[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]]
print(both_coasts([[1, 2], [4, 3]])) # -> [[0, 1], [1, 0], [1, 1]]
print(both_coasts([[1]])) # -> [[0, 0]]Stuck on the idea rather than the code? Flood Fill covers it.