Pacific Atlantic Water Flow

1. Problem & Core Objective

Given a grid of heights, the Pacific touches the top and left edges; the Atlantic touches the bottom and right. Water flows from a cell to a neighbour of equal or lower height. Return every cell from which water can reach both oceans.

1 2 2 3 5           cells reaching both:
3 2 3 4 4           (0,4) (1,3) (1,4)
2 4 5 3 1     →     (2,2) (3,0) (3,1) (4,0)
6 7 1 4 5
5 1 1 2 4

Constraints: 1 <= m, n <= 200 · 0 <= height <= 10^5

What's actually being tested: reversing the direction of the search. Asking "can this cell reach an ocean?" once per cell is O((m·n)²); asking "which cells can the ocean reach going uphill?" is two linear sweeps. It's the clearest example in the section of the search direction being the whole problem.

2. First-Principles Thought Process

The forward reading is quadratic

The obvious approach: for each of the m · n cells, DFS downhill and see whether you hit each ocean. Each DFS can touch every cell, so O((m·n)²) — at 200 × 200 that's 1.6 × 10^9.

And it's massively redundant: neighbouring cells re-explore almost identical regions.

Reverse it

Instead of "which oceans can this cell reach?", ask "which cells can this ocean reach?" — walking uphill from the border.

Why the reversal is valid

Water flows from A to B when height[A] >= height[B]. That relation is invertible: walking backwards from B to A simply requires height[A] >= height[B] — the same comparison, read the other way.

So the reverse traversal is: from each border cell, move to a neighbour whose height is greater than or equal to the current one.

if (heights[nr][nc] < heights[r][c]) continue;   // can't flow back uphill

The set of cells reached is exactly the set from which water can reach that ocean.

Two sweeps, then intersect

• Flood from all Pacific border cells → pacific[][]
• Flood from all Atlantic border cells → atlantic[][]
• The answer is every cell marked in both.

Each flood is a multi-source traversal — the whole border is seeded, exactly like question 4.

Two O(m·n) sweeps plus an O(m·n) intersection: O(m·n) overall.

The comparison direction is the bug magnet

Forward flow is >= (downhill or flat). Reverse traversal is also >=, but comparing the neighbour against the current cell rather than the other way round. Getting it backwards produces a plausible but wrong answer, so it's worth stating explicitly rather than trusting.

3. Solution Paths

Approach 1 — DFS downhill from every cell (brute force)

public List<List<Integer>> pacificAtlantic(int[][] heights) {
    List<List<Integer>> result = new ArrayList<>();
    int m = heights.length, n = heights[0].length;

    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            boolean[] reached = new boolean[2];              // {pacific, atlantic}
            dfs(heights, r, c, new boolean[m][n], reached);
            if (reached[0] && reached[1]) result.add(List.of(r, c));
        }
    return result;
}

private void dfs(int[][] h, int r, int c, boolean[][] vis, boolean[] reached) {
    if (r < 0 || c < 0) { reached[0] = true; return; }        // fell off into the Pacific
    if (r >= h.length || c >= h[0].length) { reached[1] = true; return; }
    if (vis[r][c]) return;
    vis[r][c] = true;
    for (int[] d : DIRS) {
        int nr = r + d[0], nc = c + d[1];
        boolean off = nr < 0 || nc < 0 || nr >= h.length || nc >= h[0].length;
        if (off || h[nr][nc] <= h[r][c]) dfs(h, nr, nc, vis, reached);
    }
}

• Time O((m · n)²) · Space O(m · n) per cell, reallocated m·n times

Counter-questions on this approach

⭐ "Where does the quadratic come from?"

A fresh boolean[m][n] and a full DFS per starting cell. Each DFS can reach every cell, so it's m·n traversals of m·n cells — 1.6 × 10^9 at the limit.

The redundancy is severe: two adjacent cells at similar heights explore nearly the same region, and neither result is reused.

⭐ "Could you memoise the per-cell answers?"

Not straightforwardly. A cell's reachability depends on the path taken — during a DFS you can't conclude "cell X reaches the Pacific" just because the current traversal passed through it, since the traversal might have arrived via a route that the cell itself couldn't take.

Making memoisation sound here requires care about which direction the information flows, which is precisely the hint to reverse the search instead. Then the answer for every cell is produced by one traversal, with no per-cell state at all.

"Allocating boolean[m][n] inside the loop — how bad?"

40,000 booleans allocated 40,000 times, so 1.6 × 10^9 bytes of churn. That alone would be slow, independent of the traversal cost.

Approach 2 — Reverse DFS from both oceans (optimal)

private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};

public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] pacific = new boolean[m][n];
    boolean[][] atlantic = new boolean[m][n];

    for (int r = 0; r < m; r++) {
        dfs(heights, r, 0,     pacific);        // left edge
        dfs(heights, r, n - 1, atlantic);       // right edge
    }
    for (int c = 0; c < n; c++) {
        dfs(heights, 0,     c, pacific);        // top edge
        dfs(heights, m - 1, c, atlantic);       // bottom edge
    }

    List<List<Integer>> result = new ArrayList<>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (pacific[r][c] && atlantic[r][c]) result.add(List.of(r, c));
    return result;
}

private void dfs(int[][] h, int r, int c, boolean[][] reach) {
    reach[r][c] = true;
    for (int[] d : DIRS) {
        int nr = r + d[0], nc = c + d[1];
        if (nr < 0 || nr >= h.length || nc < 0 || nc >= h[0].length) continue;
        if (reach[nr][nc]) continue;                       // already known
        if (h[nr][nc] < h[r][c]) continue;                 // cannot flow back UPHILL
        dfs(h, nr, nc, reach);
    }
}

Trace — the Pacific flood, starting at (0,0) with height 1:

• Time O(m · n) · Space O(m · n) for the two arrays

Counter-questions on this approach

⭐ "Justify the reversal. Why is walking uphill from the ocean equivalent?"

Water flows A → B exactly when height[A] >= height[B]. That's a relation between two cells, and it doesn't care which direction you traverse it.

So "cell A can reach the ocean" means there's a non-increasing path from A to the border. Reading that path backwards, from the border to A, every step is non-decreasing. Traversing uphill from the border therefore reaches exactly the cells that can flow to it.

It's not an approximation — it's the same set, enumerated from the other end.

⭐ "Why h[nr][nc] < h[r][c] and not >?"

Because I'm moving backwards along the flow. From the current cell, a neighbour is reachable in reverse if water could flow from the neighbour to me — which needs h[neighbour] >= h[current]. So I skip when it's strictly less.

Getting this inverted is the most common bug, and it produces a plausible-looking wrong answer rather than a crash. I'd trace one step to confirm: from a height-1 border cell, a height-3 neighbour must be included, because water flows 3 → 1.

⭐ "Why is flat ground included?"

Because the problem says water flows to a neighbour of equal or lower height. So equal heights flow both ways, and the reverse check must be >= rather than >.

A strict > would break flat plateaus into disconnected pieces and lose cells. The trace above shows it immediately: (0,1) at height 2 must reach (0,2) at height 2.

"Why is the reach[nr][nc] check enough as a visited marker?"

Because each array is only written by its own flood, and once a cell is marked it's already known to reach that ocean — revisiting adds nothing. The two floods are entirely independent and never interfere.

"Why seed every border cell rather than just the corners?"

Because each border cell is adjacent to the ocean directly. Water at (3,0) reaches the Pacific by flowing left, regardless of the corners.

Note the corners belong to both oceans — (0, n-1) touches the top (Pacific) and right (Atlantic) — which is handled naturally by seeding both border loops.

"What's the total work given border cells are seeded repeatedly?"

Each flood visits every cell at most once, because of the reach check. Seeding is O(m + n) calls, most of which return almost immediately. Two floods plus the final intersection is O(m · n).

"Stack depth?"

At 200 × 200 a flat grid gives a single component of 40,000 cells, so DFS could recurse that deep and overflow. I'd use an explicit stack or BFS at this size — the same concern as Number of Islands.

Comparison

4. Why the Optimal Wins

The forward version answers one question per cell and throws the traversal away. The reverse version answers the question for every cell in a single sweep, because the ocean is a shared starting point.

O((m·n)²) → O(m·n), from changing which end you search from. No cleverer data structure, no memoisation — just recognising that the flow relation is invertible and that the ocean is the better seed.

The framing worth keeping:

When "can X reach the target?" must be answered for every X, invert it to "what can the target reach?" — provided the relation is invertible. One traversal replaces n of them.

The invertibility check matters: here A → B iff h[A] >= h[B], which reads identically backwards. Not every reachability relation has that property.

5. Java Prerequisites

Reverse-flow guard — the direction to get right:

if (h[nr][nc] < h[r][c]) continue;    // skip strictly lower — cannot flow back to me

>= includes flat ground, which the problem requires.

Two reachability arrays, intersected at the end:

if (pacific[r][c] && atlantic[r][c]) result.add(List.of(r, c));

List.of(r, c) creates an immutable two-element list — fine, since the result is never mutated afterwards.

Border seeding — left/top for the Pacific, right/bottom for the Atlantic. Corners belong to both and are seeded by both loops.

6. Interview Communication Guide

Clarifying questions: Does water flow to equal heights (yes — so the comparison is >=, not >)? Which edges belong to which ocean (top and left Pacific; bottom and right Atlantic)? Output format (list of [row, col])? Does order matter (no)?

The pitch

"The direct reading is 'for each cell, can it reach both oceans?' — a DFS downhill from every cell. That's O((m·n)²), about 1.6 × 10^9 here, and it's hugely redundant since neighbouring cells re-explore the same regions.

The fix is to reverse the question: instead of 'which oceans can this cell reach?', ask 'which cells can this ocean reach?' — walking uphill from the border.

That's valid because the flow relation is invertible. Water flows A → B exactly when height[A] >= height[B], and that comparison reads the same backwards. A non-increasing path from a cell to the border, read in reverse, is a non-decreasing path from the border to the cell. So walking uphill from the ocean reaches exactly the cells that can flow into it — the same set, enumerated from the other end.

So: flood uphill from all Pacific border cells, flood uphill from all Atlantic border cells, then intersect. Two linear sweeps and an intersection — O(m·n).

The detail I'd be careful about is the comparison direction. Moving backwards, a neighbour is reachable if water could flow from it to me, which means h[neighbour] >= h[current] — so I skip when it's strictly less. Getting that inverted gives a plausible wrong answer rather than a crash, so I'd trace one step: from a height-1 border cell, a height-3 neighbour must be included, since water flows 3 → 1.

And it must be >=, not >, because the problem allows flow between equal heights — a strict comparison would break flat plateaus apart.

At 200 × 200 a flat grid is one 40,000-cell component, so I'd use BFS or an explicit stack rather than recursion."

Edge cases to volunteer:

Name the all-equal grid. Every cell reaches both oceans, and a solution using strict > returns only the border — a large, obvious discrepancy that pins the comparison down.

7. Follow-Up Questions — Modified Constraints

⭐ "Return only cells that reach the Pacific but NOT the Atlantic."

Same two floods, different combination: pacific[r][c] && !atlantic[r][c]. The sweeps produce the raw sets; the question only changes how they're combined — which is a good argument for computing both independently rather than fusing them.

⭐ "What if there were a third ocean along a diagonal?"

A third flood and a three-way intersection. The approach scales linearly in the number of oceans, whereas the forward version would still be quadratic per cell. That contrast is the clearest statement of why reversing helps.

"Water flows only strictly downhill."

The reverse check becomes h[nr][nc] <= h[r][c] → skip, i.e. require strictly greater. Flat plateaus then become impassable, which usually shrinks the answer considerably.

"What if heights could change between queries?"

Each query is O(m·n) to recompute. Incremental updates are hard — raising one cell can connect or disconnect large regions, so there's no small local fix. For frequent updates you'd look at dynamic connectivity structures, which are substantially more complex.

"Return the count rather than the coordinates."

Count during the intersection pass instead of building the list. Saves the output allocation, which at 40,000 cells is the dominant memory cost.

"What if the grid were 10^4 × 10^4?"

10^8 cells — two boolean[][] arrays is 200 MB, which is borderline. You could pack the two flags into a single byte[][] using two bits, or process in strips. Recursion is definitely out; BFS with an encoded-coordinate queue.