Pacific Atlantic Water Flow

The problem

You are given heights, a grid in which each cell is a piece of land with a height. The Pacific Ocean touches the top and left edges of the grid, and the Atlantic Ocean touches the bottom and right edges. Rain that falls on a cell can flow to the cell above, below, left or right of it if that cell is not higher, and from any edge cell into the ocean touching that edge. Return every cell from which water can reach both oceans, each once, as [row, column], counting from 0. The cells may be in any order.

What to write

function solve(heights: number[][]): number[][]

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]]

Output
[[0,0]]

Constraints

Return coordinates in any order; the matrix is nonempty.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   Water crosses level ground but never climbs. A cell on the top or left edge already touches the Pacific, and a cell on the bottom or right edge touches the Atlantic. So the top-right and bottom-left corners reach both oceans without moving: in the first example those are [0, 4] and [4, 0].

2. Hint 2: Ask a smaller question

   In the first example, look at the 5 in the middle and the 3 to its right. That 3 reaches the Atlantic, because the 1 beside it lies on the right edge. Knowing that, what can you say about the 5 without following its water at all? Which other neighbors of the 3 does the same reasoning cover?

3. Hint 3: Name the pattern

   The question "can this cell reach that edge?" is asked for every cell, which is the signal to search from the edge instead: start at an ocean's edge cells and climb to every neighbor that is not lower. Visiting everything reachable while remembering what you have reached is a graph traversal with a visited set. Run it once per ocean. Read the lesson on graph traversal with a visited set.

4. Hint 4: State the invariant

   Every cell a search has marked can send its water to that search's ocean: it lies on the ocean's edge, or it was reached from a marked neighbor that is not higher, so its water can step down to that neighbor and go on from there.

5. Hint 5: Sketch the pseudocode

   search(edge cells): mark them and put them on a waiting list. Until the list is empty: take a cell; mark and add each of its four neighbors that is inside the grid, not lower than the cell and not marked yet. Return the marked cells. Answer: the cells marked by both search(left column, top row) and search(right column, bottom row).

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Reverse the flow: search uphill from each ocean’s boundary, then intersect the two reachable sets.

The slow way

For every cell, follow the water: walk to neighbors that are not higher, remembering where you have been so that level ground does not send you in circles, and see whether the walk touches both a Pacific edge and an Atlantic edge. It is correct, but every cell starts a new walk that can cover the whole grid: about cells × cells steps.

The insight

Turn the water round. Instead of asking where each cell's water can go, ask which cells can send water to one ocean: start on that ocean's edge and climb to every neighbor that is not lower. One search finds them all. Do it for both oceans and keep the cells that both searches found.

Step by step

1. Measure the grid: its edges are where the two oceans begin. Row 0 and column 0 touch the Pacific; the last row and the last column touch the Atlantic. The size is also needed to refuse a neighbor that lies outside the grid.
2. One search starts from an ocean's edge cells: mark and queue them. An edge cell drains into its ocean without moving, so it counts as reached from the start. A queue is a waiting line: cells join at the back and are taken from the front.
3. Take the next cell in the queue and look at its four neighbors. Water moves only up, down, left or right, so those four cells are the only ones whose water could flow straight into this cell.
4. Climb to a neighbor that is not lower and not reached before. Water runs from that neighbor down into this cell only if the neighbor is at least as high. A cell already marked is skipped, which keeps level ground from being walked for ever.
5. No cell is left waiting: every cell reached drains to that ocean. Each marked cell was reached by water steps taken backwards, so its water can retrace them down to the edge. A cell that drains there cannot be missed, as the search can climb along its path.
6. Search from the Pacific's edges, then from the Atlantic's edges. The two searches are independent, each with its own set of marked cells. A cell reached for one ocean must still be free to be reached for the other.
7. Return the cells that both searches reached. A cell is asked for only if its water reaches the Pacific and the Atlantic, which means it was marked by the first search and by the second.

The same numbered steps are the comments in each solution.

function solve(heights) {
  // 1. Measure the grid: its edges are where the two oceans begin
  const rows = heights.length,
    cols = heights[0].length;
  function reach(seeds) {
    // 2. One search starts from an ocean's edge cells: mark and queue them
    // A Set compares two arrays by identity, not by what they hold,
    // so each cell is remembered as the text "row,column".
    const seen = new Set();
    const q = seeds;
    for (const [r, c] of seeds) seen.add(r + "," + c);
    // 3. Take the next cell in the queue and look at its four neighbors
    // i walks along the queue, so no cell has to be removed from its front.
    for (let i = 0; i < q.length; i++) {
      const [r, c] = q[i];
      for (const [a, b] of [
        [r + 1, c],
        [r - 1, c],
        [r, c + 1],
        [r, c - 1],
      ])
        // 4. Climb to a neighbor that is not lower and not reached before
        if (
          a >= 0 &&
          a < rows &&
          b >= 0 &&
          b < cols &&
          heights[a][b] >= heights[r][c] &&
          !seen.has(a + "," + b)
        ) {
          seen.add(a + "," + b);
          q.push([a, b]);
        }
    }
    // 5. No cell is left waiting: every cell reached drains to that ocean
    return seen;
  }
  // 6. Search from the Pacific's edges, then from the Atlantic's edges
  // The corner where the two edges meet is listed twice, which does no harm.
  // Array.from({ length: rows }, (_, r) => [r, 0]) lists the left column:
  // [0, 0], [1, 0] and so on, one cell per row.
  const pacific = reach([
    ...Array.from({ length: rows }, (_, r) => [r, 0]),
    ...Array.from({ length: cols }, (_, c) => [0, c]),
  ]);
  const atlantic = reach([
    ...Array.from({ length: rows }, (_, r) => [r, cols - 1]),
    ...Array.from({ length: cols }, (_, c) => [rows - 1, c]),
  ]);
  // 7. Return the cells that both searches reached
  // Each "row,column" text is split back into a pair of numbers.
  return [...pacific]
    .filter((cell) => atlantic.has(cell))
    .map((cell) => cell.split(",").map(Number));
}

function solve(heights: number[][]): number[][] {
  // 1. Measure the grid: its edges are where the two oceans begin
  const rows = heights.length,
    cols = heights[0].length;
  function reach(seeds: number[][]): Set<string> {
    // 2. One search starts from an ocean's edge cells: mark and queue them
    // A Set compares two arrays by identity, not by what they hold,
    // so each cell is remembered as the text "row,column".
    const seen = new Set<string>();
    const q = seeds;
    for (const [r, c] of seeds) seen.add(r + "," + c);
    // 3. Take the next cell in the queue and look at its four neighbors
    // i walks along the queue, so no cell has to be removed from its front.
    for (let i = 0; i < q.length; i++) {
      const [r, c] = q[i];
      for (const [a, b] of [
        [r + 1, c],
        [r - 1, c],
        [r, c + 1],
        [r, c - 1],
      ])
        // 4. Climb to a neighbor that is not lower and not reached before
        if (
          a >= 0 &&
          a < rows &&
          b >= 0 &&
          b < cols &&
          heights[a][b] >= heights[r][c] &&
          !seen.has(a + "," + b)
        ) {
          seen.add(a + "," + b);
          q.push([a, b]);
        }
    }
    // 5. No cell is left waiting: every cell reached drains to that ocean
    return seen;
  }
  // 6. Search from the Pacific's edges, then from the Atlantic's edges
  // The corner where the two edges meet is listed twice, which does no harm.
  // Array.from({ length: rows }, (_, r) => [r, 0]) lists the left column:
  // [0, 0], [1, 0] and so on, one cell per row.
  const pacific = reach([
    ...Array.from({ length: rows }, (_, r) => [r, 0]),
    ...Array.from({ length: cols }, (_, c) => [0, c]),
  ]);
  const atlantic = reach([
    ...Array.from({ length: rows }, (_, r) => [r, cols - 1]),
    ...Array.from({ length: cols }, (_, c) => [rows - 1, c]),
  ]);
  // 7. Return the cells that both searches reached
  // Each "row,column" text is split back into a pair of numbers.
  return [...pacific]
    .filter((cell) => atlantic.has(cell))
    .map((cell) => cell.split(",").map(Number));
}

from collections import deque


def solve(heights):
    # 1. Measure the grid: its edges are where the two oceans begin
    rows, cols = len(heights), len(heights[0])

    def reach(seeds):
        # 2. One search starts from an ocean's edge cells: mark and queue them
        seen = set(seeds)
        # A deque is a list that is fast at both ends: append adds at the back,
        # popleft takes from the front.
        queue = deque(seeds)
        # 3. Take the next cell in the queue and look at its four neighbors
        while queue:
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                # 4. Climb to a neighbor that is not lower and not reached before
                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and heights[nr][nc] >= heights[r][c]
                    and (nr, nc) not in seen
                ):
                    seen.add((nr, nc))
                    queue.append((nr, nc))
        # 5. No cell is left waiting: every cell reached drains to that ocean
        return seen

    # 6. Search from the Pacific's edges, then from the Atlantic's edges
    # The corner where the two edges meet is listed twice, which does no harm.
    pacific = reach([(r, 0) for r in range(rows)] + [(0, c) for c in range(cols)])
    atlantic = reach(
        [(r, cols - 1) for r in range(rows)] + [(rows - 1, c) for c in range(cols)]
    )
    # 7. Return the cells that both searches reached
    # Between two sets, & keeps what is in both. Each cell becomes a list again.
    return [[r, c] for r, c in pacific & atlantic]

Example 1, traced

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]]

Why it works

A search starts with its ocean's edge cells and marks a new cell only by stepping from a marked cell to a neighbor that is not lower: a water step taken backwards. So every marked cell has a path of water steps to that edge, and every cell with such a path gets marked, because the search can walk it in reverse. Cells marked by both searches reach both oceans.

Time and space

Time O(rows · cols), extra space O(rows · cols). The grid has rows · cols cells. Each search marks a cell at most once and takes it from the queue at most twice, checking four neighbors each time: O(rows · cols) time for the two searches. Marks and queues grow with the number of cells: O(rows · cols) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Climb to a neighbor that is equal or higher, not only higher: water crosses level ground. With a strict comparison the first example loses [1, 4], whose only way to the Pacific leads over a neighbor of the same height.
• Give each search its own set of marked cells. With one shared set, the second search cannot climb into anything the first marked and never reaches cells that drain to both oceans, such as [2, 2] in the first example.
• In JavaScript a Set treats two arrays with the same numbers as different, so a cell kept as an array is never found again. The first example never ends: level cells keep queueing each other. Store each cell as text.

Pattern

Graph traversal with a visited set. Builds on Number of Islands and Clone Graph.

Keep going