A hydrology service is given a height raster of a coastal island: Pacific along the top and left, Atlantic along the bottom and right. Product wants every cell whose rain can drain to both oceans — dual-drainage sites for a flood model. The intern nested a downhill neighbor walk from every cell, hunting for both shorelines. An 8×8 fixture in staging returned. A million-cell DEM in production was still walking when the request timed out.

Pacific Atlantic Water Flow asks which cells can drain to both oceans. This is an interview writeup, not a layout lecture. The graphs post owns the layout; the BFS post owns the frontier. Here we only care about four neighbor deltas, seeding both shores, and intersecting two reach sets. Rotting Oranges is the same multi-source seed; that prompt counts minutes. This one does not.

The problem

Given an m × n int[][] heights, rain at (r, c) may flow to a 4-neighbor — up, down, left, right — whose height is equal or lower. The Pacific Ocean touches the top row and the left column. The Atlantic Ocean touches the bottom row and the right column. Return every [r, c] that can reach both oceans. Order of the list does not matter.

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

→  [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

1 2
4 3

→  [[0,1],[1,0],[1,1]]     (0,0) is Pacific-only; it cannot climb

1                 →  [[0,0]]     one cell sits on every border

Note: Off-board is a wall of the matching ocean, not a wrap. Bounds-check first, then compare heights. A 4-direction int[][] dirs table is the neighbor list; do not special-case four ifs unless the board asks you to name them. Corner (0, n-1) and (m-1, 0) already touch both oceans. (0, 0) is Pacific only; (m-1, n-1) is Atlantic only.

Walking downhill from every cell is the honest brute force

A neighbor walk with no mark never returns. Equal-height neighbors bounce. Staging’s hang was that plateau.

The honest version starts at every cell, walks downhill (equal or lower) with a local seen set, and accepts the cell if that walk hits both a Pacific border and an Atlantic border. Correct. Quadratic.

List<List<Integer>> pacificAtlanticRestart(int[][] heights) {
    int m = heights.length;
    int n = heights[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    List<List<Integer>> ans = new ArrayList<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            boolean[] oceans = new boolean[2];
            downhill(heights, r, c, dirs, new HashSet<>(), oceans);
            if (oceans[0] && oceans[1]) {
                ans.add(List.of(r, c));
            }
        }
    }
    return ans;
}

void downhill(int[][] heights, int r, int c, int[][] dirs, Set<Integer> seen, boolean[] oceans) {
    if (!seen.add(r * heights[0].length + c)) {
        return;
    }
    if (r == 0 || c == 0) {
        oceans[0] = true;
    }
    if (r == heights.length - 1 || c == heights[0].length - 1) {
        oceans[1] = true;
    }
    if (oceans[0] && oceans[1]) {
        return;
    }
    for (int[] d : dirs) {
        int nr = r + d[0];
        int nc = c + d[1];
        if (nr < 0 || nr >= heights.length || nc < 0 || nc >= heights[0].length) {
            continue;
        }
        if (heights[nr][nc] <= heights[r][c]) {
            downhill(heights, nr, nc, dirs, seen, oceans);
        }
    }
}

At an 8×8 fixture this is a rounding error. On a full raster you restart an O(mn) walk from every cell: you paid a downhill search per cell for a question two inland floods already answer.

Seed both shores, walk inland, intersect

Rain flows to equal-or-lower neighbors, so the reverse walk from an ocean only steps to equal-or-higher heights — inland, the terrain goes up (or stays). Seed every Pacific-border cell into one flood, every Atlantic-border cell into another, and keep the cells both floods mark.

Same 4-dir paint as Flood Fill; the seeds are the two shores, not a click. Same multi-source ArrayDeque as Rotting Oranges; you do not need hop count.

1 2
4 3

Pacific seeds (top + left):      (0,0)=1  (1,0)=4  (0,1)=2
Atlantic seeds (right + bottom): (0,1)=2  (1,1)=3  (1,0)=4

Pacific inland (≥ current), queue (0,0), (1,0), (0,1):
  poll (0,0)=1   (0,1) and (1,0) already marked
  poll (1,0)=4   (1,1)=3 < 4 skip
  poll (0,1)=2   (1,1)=3 ≥ 2 → mark P
  poll (1,1)=3   neighbors already P
  P = all four cells

Atlantic inland, queue (0,1), (1,1), (1,0):
  poll (0,1)=2   (0,0)=1 < 2 skip   (1,1) already
  poll (1,1)=3   neighbors already A
  poll (1,0)=4   (0,0)=1 skip
  A = {(0,1),(1,0),(1,1)}     not (0,0)

intersect →  [[0,1],[1,0],[1,1]]

Mark a cell when you offer it so a plateau is not queued twice. Four deltas, bounds-check, skip any neighbor shorter than the cell you just left. The Java is that pair of floods; the return is the intersection.

List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length;
    int n = heights[0].length;
    int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    boolean[][] pacific = new boolean[m][n];
    boolean[][] atlantic = new boolean[m][n];
    Deque<int[]> pacificQ = new ArrayDeque<>();
    Deque<int[]> atlanticQ = new ArrayDeque<>();
    for (int r = 0; r < m; r++) {
        seed(pacific, pacificQ, r, 0);
        seed(atlantic, atlanticQ, r, n - 1);
    }
    for (int c = 0; c < n; c++) {
        seed(pacific, pacificQ, 0, c);
        seed(atlantic, atlanticQ, m - 1, c);
    }
    inland(heights, pacific, pacificQ, dirs);
    inland(heights, atlantic, atlanticQ, dirs);
    List<List<Integer>> ans = new ArrayList<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (pacific[r][c] && atlantic[r][c]) {
                ans.add(List.of(r, c));
            }
        }
    }
    return ans;
}

void seed(boolean[][] ocean, Deque<int[]> q, int r, int c) {
    if (ocean[r][c]) {
        return;
    }
    ocean[r][c] = true;
    q.offer(new int[] { r, c });
}

void inland(int[][] heights, boolean[][] ocean, Deque<int[]> q, int[][] dirs) {
    int m = heights.length;
    int n = heights[0].length;
    while (!q.isEmpty()) {
        int[] cell = q.poll();
        int r = cell[0];
        int c = cell[1];
        for (int[] d : dirs) {
            int nr = r + d[0];
            int nc = c + d[1];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n || ocean[nr][nc]) {
                continue;
            }
            if (heights[nr][nc] < heights[r][c]) {
                continue;
            }
            ocean[nr][nc] = true;
            q.offer(new int[] { nr, nc });
        }
    }
}

Time is O(mn) — each cell is offered onto each ocean’s queue at most once, and each dequeued cell looks at four neighbors. Space is O(mn) for the two mark grids and the queues. Use Deque and ArrayDeque, not java.util.Stack, not ArrayList.remove(0). Recursive DFS from the same seeds is the same bound; a solid uphill slope is a million frames.

Note: Inland means equal-or-higher. Flip the comparison and you flood downhill from the shore — the valleys, none of the ridges that actually drain to that ocean. Corner cells in both seed loops are why seed bails when already marked.

What interviewers usually poke next

  • DFS from the same seeds. Same inland step, recursion or push / pop on an ArrayDeque. Not java.util.Stack. Reachability does not care which frontier you pick.
  • Rotting Oranges. Multi-source BFS where the hop count is the answer. Do not paste that clock into this return.
  • Flood Fill. One seed, recolor the blob. This prompt seeds two borders and intersects.
  • Surrounded Regions. Flood from the border; the interior leftover is the capture. Same “start at the edge” instinct, different predicate.
  • Equal heights / 1×1. = flows. A single cell sits on every border, so it is in the answer.

You are done with this problem when you can say, out loud, why a downhill walk from every cell is correct, why reversing the flow lets you seed the oceans, and why the answer is the intersection of two inland floods.