Cells whose rain reaches both coasts

Reverse the flow. Start a BFS from every cell on the west edges and climb to neighbours of equal or greater height; that marks every cell that drains west. Do the same from the east edges. The answer is the cells in both sets. O(R·C) time and space.

Searching from each cell downhill is O((R·C)²); reversing the direction shares work between cells.

This is multi-source BFS again, with 'uphill' as the edge rule.

Sorting the output makes the answer deterministic for testing.

from collections import deque


STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1))


def both_coasts(height: list[list[int]]) -> list[list[int]]:
    rows, cols = len(height), len(height[0]) if height else 0

    def climb(starts: list[tuple[int, int]]) -> set[tuple[int, int]]:
        seen = set(starts)
        queue = deque(starts)
        while queue:
            r, c = queue.popleft()
            for dr, dc in STEPS:
                y, x = r + dr, c + dc
                inside = 0 <= y < rows and 0 <= x < cols
                if (inside and (y, x) not in seen
                        and height[y][x] >= height[r][c]):
                    seen.add((y, x))
                    queue.append((y, x))
        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)

Common mistakes

• Climbing to strictly higher cells only, which misses flat plateaus.
• Running the downhill search from every cell and timing out on large maps.

Say 'reverse the direction and start from the coasts'. That reframing is the whole insight.

Follow-up questions

Think of your answer first, then open the hint.

1. What if water can flow diagonally?

   Show hint

   Add the four diagonal neighbours to both searches.

2. How would you count cells draining to exactly one coast?

   Show hint

   Symmetric difference of the two sets.