progress

~/problems / Graphs / DFS and connected components

Pacific Atlantic Water Flow

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium ~25 min

Implement pacific_atlantic(heights) -> list[list[int]].

heights is a rectangular grid of non-negative integers describing an island's elevation. The Pacific touches the top and left edges of the grid, the Atlantic touches the bottom and right edges. Rain on a cell can move to a side-sharing neighbour whose height is less than or equal to the current cell's, and it drains into an ocean from any cell on an edge touching that ocean.

Return the coordinates [r, c] of every cell from which water can reach both oceans. Any order is accepted.

pacific_atlantic([
    [1, 2, 3],
    [8, 9, 4],
    [7, 6, 5],
])
# [[0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
A 3 by 3 height map with the Pacific on the top and left and the Atlantic on the bottom and right; every cell except the top-left two can drain to both oceans.

Here [0, 0] and [0, 1] only reach the Pacific, since everything to their right or below is higher.

Grids go up to 150×150. Avoid deep recursion (Python's default limit is about 1,000 frames).

⭐ Bonus: a speed test on a large basin earns a star in O(rows·cols). Searching downhill from every cell separately is too slow for it.

Show hint

Instead of asking where each cell's water can go, ask which cells can send water to a given ocean, starting from that ocean's edge.

Topic: DFS and connected components. Iterative DFS / flood fill; count and label components.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc