Blind 75 · Graphs

Pacific Atlantic Water Flow

Medium

Problem

An island's terrain is an m x n grid of heights. The Pacific touches its top and left edges, the Atlantic its bottom and right. Rain flows from a cell to any horizontally or vertically adjacent cell of equal or lower height, and off a matching edge into that ocean.
Return every cell from which water can reach BOTH oceans, as [row, column] pairs sorted by row and then by column.

Examples

Example 1:
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]]

Example 2:
Input: heights = [[1]]
Output: [[0,0]]

Example 3:
Input: heights = [[1,2],[4,3]]
Output: [[0,1],[1,0],[1,1]]
Explanation: the 1 at [0,0] is walled in by higher ground on both inland sides.

Example 4:
Input: heights = [[3,3,3],[3,1,3],[3,3,3]]
Output: [[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]
Explanation: the level ring reaches everywhere; the pit in the middle reaches nothing.

Constraints

1 <= m, n <= 200
0 <= heights[i][j] <= 10^5

Prerequisites

Graph traversal — DFS and BFS, and a visited set as the thing that makes both terminate.
Union-find for connectivity questions; topological order for dependency ones.

How to think about it

1. Climb From the Oceans Optimal

Intuition

Asking "where can this cell drain to" from every cell re-walks the same paths endlessly. Reverse the question: start AT each ocean and climb to equal-or-higher neighbours, which marks everything that can drain into it. Two such floods, one per ocean, and the answer is the intersection — each cell is visited a constant number of times instead of starting its own search.

Algorithm

1. Flood from every Pacific-edge cell, moving only to equal-or-higher neighbours.
2. Flood the same way from every Atlantic edge.
3. Collect cells reached by both, walking the grid row-major for the required order.

Time & Space

Time O(m x n). Space O(m x n). The per-cell downhill search is O((mn)^2), which this replaces.