Pacific Atlantic water flow

Rain flows to neighbours that are not higher. Which cells drain into both oceans? Search backwards, uphill, from each ocean's coast and intersect the two reach sets.

Time O(rows × cols)Space O(rows × cols)Code C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Following the rain downhill from every cell would repeat the same work many times. Run it backwards: start from the cells touching an ocean and walk uphill, stepping to a neighbour only if it is at least as high, because then water can flow from it down to where we stand. Every cell this reaches drains into that ocean. Do it once for the Pacific (top and left edges) and once for the Atlantic (bottom and right edges). The answer is the cells in both sets.

Code

public IList<IList<int>> PacificAtlantic(int[][] heights) {
    int m = heights.Length, n = heights[0].Length;
    var pac = new bool[m, n];
    var atl = new bool[m, n];
    var pq = new Queue<(int r, int c)>();
    var aq = new Queue<(int r, int c)>();
    for (int r = 0; r < m; r++) { Seed(pq, pac, r, 0); Seed(aq, atl, r, n - 1); }
    for (int c = 0; c < n; c++) { Seed(pq, pac, 0, c); Seed(aq, atl, m - 1, c); }
    Bfs(heights, pq, pac);
    Bfs(heights, aq, atl);
    var result = new List<IList<int>>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (pac[r, c] && atl[r, c]) result.Add(new[] { r, c });
    return result;
}

static void Seed(Queue<(int r, int c)> q, bool[,] seen, int r, int c) {
    if (seen[r, c]) return;
    seen[r, c] = true; // a coast cell drains straight into the ocean
    q.Enqueue((r, c));
}

static readonly (int dr, int dc)[] Dirs = { (1, 0), (-1, 0), (0, 1), (0, -1) };

static void Bfs(int[][] h, Queue<(int r, int c)> q, bool[,] seen) {
    while (q.Count > 0) {
        var (r, c) = q.Dequeue();
        foreach (var (dr, dc) in Dirs) {
            int nr = r + dr, nc = c + dc;
            if (nr < 0 || nc < 0 || nr >= h.Length || nc >= h[0].Length || seen[nr, nc]) continue;
            if (h[nr][nc] < h[r][c]) continue; // lower: water cannot climb from there to here
            seen[nr, nc] = true; // water from (nr, nc) runs down to (r, c), then to the ocean
            q.Enqueue((nr, nc));
        }
    }
}

Tips

The step rule is "neighbour ≥ current", the reverse of how rain falls. Equal heights pass both ways, because water also flows across flat ground.
Each search visits a cell at most once, so the whole thing is O(rows × cols), instead of a fresh search from every cell.
The top-right and bottom-left corners touch both oceans, so they are always in the answer.

In the .NET library

bool[m, n] is a rectangular array, and (int r, int c) value tuples go into Queue<T> without a heap allocation per cell. The foreach over Dirs deconstructs each tuple into dr and dc.