Loading…

mediumGraphsLC #417Frequently asked

Pacific Atlantic Water Flow

Q: How do you solve Pacific Atlantic Water Flow using the Brute Force — Flow Simulation From Every Cell approach?

When to use it: Mention to anchor why reversal is needed, then discard — it's quadratic in the number of cells. Translate the problem directly: a cell drains to an ocean if a downhill (non-increasing) path leads from it to that ocean's edge. **Per-cell search.** For each cell, run a DFS/BFS that only steps to neighbours with height ≤ the current cell's height (the natural flow direction). Flag whether the search ever lands on a Pacific border and whether it lands on an Atlantic border. If both, add the cell to the answer. **Why it's too slow.** You repeat an O(m·n) traversal from every one of the m·n cells, giving O((m·n)²) — roughly 1.6 billion operations on a 200×200 grid. Correct but not acceptable. The waste is obvious: the same downhill paths get re-explored from many starting points. That redundancy is the cue to flip the direction of the search. Time complexity: O((m × n)²). Space complexity: O(m × n).

Q: How do you solve Pacific Atlantic Water Flow using the Reverse Multi-Source DFS From Both Oceans (Optimal) approach?

When to use it: The expected answer. Lead with the reversal: 'climb uphill from each ocean's border and intersect the two reachable sets'. The whole problem cracks open once you reverse the flow. **The reversal insight.** Water flows from high to low. A cell drains to the Pacific iff there's a non-increasing path from it to a Pacific border. Equivalently, starting *at* a Pacific border and walking to neighbours that are *higher or equal*, you can reach exactly those cells that drain into the Pacific. So instead of n thousand downhill searches, we do one *uphill* search seeded from the ocean. **Two multi-source traversals.** Seed a DFS (or BFS) with *all* Pacific border cells at once — the entire top row and left column — and flood inward, only stepping to a neighbour whose height is `>= current`. Every cell reached lands in the `pacific` set. Repeat from the Atlantic borders (bottom row + right column) into the `atlantic` set. 'Multi-source' just means we start the search from many seeds simultaneously rather than restarting per seed. **Intersect.** A cell that appears in both sets can drain to both oceans — that's the answer. Walk the grid once and collect cells present in both visited matrices. **Why `>=` not `>`.** Forward flow is allowed when the neighbour is ≤ current, which includes equal heights. Reversing, we move from current to a neighbour that is ≥ current — and equal-height neighbours must still be traversable, so the comparison is `>=`. Time complexity: O(m × n). Space complexity: O(m × n).

LCPractice

Graphs · 4 of 34 · 10 min

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at (r, c).

The island receives a lot of rain, and rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

In plain English

A cell drains to an ocean if there's a non-increasing path of heights from it to that ocean's border. We want cells that drain to BOTH oceans. Simulating outward from each cell is wasteful; reversing to climb inward from each ocean computes the two reachable sets in two passes.

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]]
Note: These cells have a non-increasing path to both the Pacific (top/left) and Atlantic (bottom/right) borders.

Example 2

Input: heights = [[1]]
Output: [[0,0]]
Note: A single cell borders all four edges, so it trivially reaches both oceans.

Example 3

Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]
Note: Small grid where every cell can reach both oceans via the borders.

Constraints

m == heights.length
n == heights[r].length
1 ≤ m, n ≤ 200
0 ≤ heights[r][c] ≤ 10⁵

Clarifying questions4First question: Can water flow between equal-height cells?Explore questions

Q1.Can water flow between equal-height cells?
Yes — flow allowed when neighbour height ≤ current. So in the reversed climb, I move when neighbour ≥ current, using >= (equal heights pass).
Q2.Which edges touch which ocean?
Pacific = top row and left column; Atlantic = bottom row and right column. Corner cells border both.
Q3.Does the output order matter?
No — any order of the qualifying coordinates is accepted.
Q4.How big is the grid?
Up to 200×200 = 40,000 cells. The reverse approach is O(mn); the brute-force per-cell simulation would be ~O((mn)²) and too slow.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Don't simulate flow from every cell — reverse it. Start from the ocean border cells and climb to neighbours of equal or greater height, marking which cells can reach the Pacific and which can reach the Atlantic. The answer is the intersection: cells reachable from both oceans. Two flood fills over the grid → O(rows × cols).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you avoid the O((mn)²) brute force by reversing the flow and seeding multi-source traversals from the borders, then intersecting two reachability sets.

Where candidates slip

Running a separate flow simulation from every cell (quadratic), using `>` instead of `>=`, or only seeding from corners instead of entire border rows/columns.

How to stand out

Explain the reversal insight crisply ('climb from the ocean'), seed both border sets, use a visited matrix per ocean, intersect, and note BFS works identically if recursion depth is a concern.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Flow Simulation From Every Cell	`O((m × n)²)`	`O(m × n)`	Mention to anchor why reversal is needed, then discard — it's quadratic in the number of cells.	Read
2	Reverse Multi-Source DFS From Both Oceans (Optimal)Optimal	`O(m × n)`	`O(m × n)`	The expected answer. Lead with the reversal: 'climb uphill from each ocean's border and intersect the two reachable sets'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCells draining to both oceansSimulate from each cell?Brute forceReverse itExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Flow Simulation From Every Cell

TimeO((m × n)²)SpaceO(m × n)

Mention to anchor why reversal is needed, then discard — it's quadratic in the number of cells.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Literal reading: for each cell, can water flow downhill from it all the way to each ocean?

2Hint 2Explore hint

From each starting cell, DFS/BFS following non-increasing heights; record whether you reach a Pacific border and whether you reach an Atlantic border.

3Hint 3Explore hint

A cell qualifies if a single search from it touches both. But you'd repeat this search from all m·n cells — that's the bottleneck.

A · Core idea

Translate the problem directly: a cell drains to an ocean if a downhill (non-increasing) path leads from it to that ocean's edge.

Per-cell search. For each cell, run a DFS/BFS that only steps to neighbours with height ≤ the current cell's height (the natural flow direction). Flag whether the search ever lands on a Pacific border and whether it lands on an Atlantic border. If both, add the cell to the answer.

Why it's too slow. You repeat an O(m·n) traversal from every one of the m·n cells, giving O((m·n)²) — roughly 1.6 billion operations on a 200×200 grid. Correct but not acceptable. The waste is obvious: the same downhill paths get re-explored from many starting points. That redundancy is the cue to flip the direction of the search.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

heights = [[2,1],[1,2]]

(0,0)=2

borders both Pacific(top/left); also can it reach Atlantic? downhill to (0,1)=1,(1,0)=1

Statereaches both

Final result[[0,0],[0,1],[1,0],[1,1]]

C · Code with teaching comments

Reference implementation preview// Illustrative only — O((m*n)^2), too slow for the constraints. public List<List<Integer>> pacificAtlantic(int[][] heights) { int m = heights.length, n = heights[0].length; List<List<Integer>> res = new ArrayList<>(); for (int r = 0; r < m; r++) {Explore the full code

solution.javaJava

Brute Force — Flow Simulation From Every Cell — reference

3 teaching notes

1
// Illustrative only — O((m*n)^2), too slow for the constraints.
2
public List<List<Integer>> pacificAtlantic(int[][] heights) {
3
    int m = heights.length, n = heights[0].length;
4
    List<List<Integer>> res = new ArrayList<>();
5
    for (int r = 0; r < m; r++) {
6
        for (int c = 0; c < n; c++) {
7
            // Track per-cell whether a downhill search hits each ocean.
8
            boolean[] reach = new boolean[2]; // [pacific, atlantic]
9
            boolean[][] seen = new boolean[m][n];
10
            // A full O(m·n) traversal per starting cell — the source of the quadratic
11
            // cost.
12
            flow(heights, r, c, seen, reach);
13
            if (reach[0] && reach[1]) {
14
                res.add(Arrays.asList(r, c));
15
            }
16
        }
17
    }
18
    return res;
19
}
20
// flow() DFS downhill, setting reach[] when a border is touched.

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO((m × n)²) timeO(m × n) spaceOpen the invariant and proofExplore the proof

When 'can X reach a target?' must be answered for many X but few targets, invert it: compute 'what can each target reach?' once per target. Here there are only two targets (the two oceans) but thousands of cells — so two reverse searches crush thousands of forward ones.

ComplexityO((m × n)²) time, O(m × n) space — Each of the m·n cells launches a traversal that can visit up to m·n cells → O((m·n)²). The visited bookkeeping per search is O(m·n) space.

E · Edge cases and pitfalls3Re-running a full traversal per cell — quadratic and times out at 200×200.Explore edge cases

Pitfalls

Re-running a full traversal per cell — quadratic and times out at 200×200.
Resetting the visited structure incorrectly between cells.
Confusing flow direction (should be downhill, neighbour ≤ current, in the forward simulation).

03.2

Approach 2 of 2 · Optimal

Reverse Multi-Source DFS From Both Oceans (Optimal)

TimeO(m × n)SpaceO(m × n)

The expected answer. Lead with the reversal: 'climb uphill from each ocean's border and intersect the two reachable sets'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Flip the question. Instead of 'which cells reach the ocean?', ask 'which cells can the ocean reach if water flowed backward (uphill)?'

2Hint 2Explore hint

Seed a DFS from every Pacific border cell (top row + left column) and climb to neighbours with height ≥ current, marking a `pacific` set. Do the same from the Atlantic borders into an `atlantic` set.

3Hint 3Explore hint

Any cell in both sets can drain to both oceans. Intersect the two visited sets for the answer.

A · Core idea

The whole problem cracks open once you reverse the flow.

The reversal insight. Water flows from high to low. A cell drains to the Pacific iff there's a non-increasing path from it to a Pacific border. Equivalently, starting at a Pacific border and walking to neighbours that are higher or equal, you can reach exactly those cells that drain into the Pacific. So instead of n thousand downhill searches, we do one uphill search seeded from the ocean.

Two multi-source traversals. Seed a DFS (or BFS) with all Pacific border cells at once — the entire top row and left column — and flood inward, only stepping to a neighbour whose height is >= current. Every cell reached lands in the pacific set. Repeat from the Atlantic borders (bottom row + right column) into the atlantic set. 'Multi-source' just means we start the search from many seeds simultaneously rather than restarting per seed.

Intersect. A cell that appears in both sets can drain to both oceans — that's the answer. Walk the grid once and collect cells present in both visited matrices.

Why `>=` not `>`. Forward flow is allowed when the neighbour is ≤ current, which includes equal heights. Reversing, we move from current to a neighbour that is ≥ current — and equal-height neighbours must still be traversable, so the comparison is >=.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

heights = [[1,2,2,3,5],[3,2,3,4,4],...] (5×5 sample)

Array state

pacific

reach from top/left

ocean ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

C · Code with teaching comments

solution.javaJava

Reverse Multi-Source DFS From Both Oceans (Optimal) — optimal

3 teaching notes

1
public List<List<Integer>> pacificAtlantic(int[][] heights) {
2
    int m = heights.length, n = heights[0].length;
3
    boolean[][] pacific = new boolean[m][n];
4
    boolean[][] atlantic = new boolean[m][n];
5
    for (int r = 0; r < m; r++) {
6
        dfs(heights, r, 0, pacific);       // left col → Pacific
7
        dfs(heights, r, n - 1, atlantic);  // right col → Atlantic
8
    }
9
    for (int c = 0; c < n; c++) {
10
        dfs(heights, 0, c, pacific);       // top row → Pacific
11
        dfs(heights, m - 1, c, atlantic);  // bottom row → Atlantic
12
    }
13
    List<List<Integer>> res = new ArrayList<>();
14
    for (int r = 0; r < m; r++) {
15
        for (int c = 0; c < n; c++) {
16
            if (pacific[r][c] && atlantic[r][c]) {
17
                res.add(Arrays.asList(r, c));
18
            }
19
        }
20
    }
21
    return res;
22
}
23
 
24
private void dfs(int[][] h, int r, int c, boolean[][] ocean) {
25
    ocean[r][c] = true;
26
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
27
    for (int[] d : dirs) {
28
        int nr = r + d[0], nc = c + d[1];
29
        if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length
30
                && !ocean[nr][nc] && h[nr][nc] >= h[r][c]) {
31
            dfs(h, nr, nc, ocean);
32
        }
33
    }
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(m × n) timeO(m × n) spaceOpen the invariant and proofExplore the proof

Two reverse floods replace tens of thousands of forward ones. The trick generalises: whenever the targets are few and the sources are many, search backward from the targets. Marking visited per ocean (not globally) is essential — a cell can belong to both reachable sets.

ComplexityO(m × n) time, O(m × n) space — Each ocean's traversal visits every cell at most once (a per-ocean visited matrix), so each is O(m·n); two of them is still O(m·n). The two visited matrices are O(m·n) space.

E · Edge cases and pitfalls6single cell [[1]] — Borders all edges; in both sets → [[0,0]].Explore edge cases

Edge cases handled

single cell [[1]]Borders all edges; in both sets → [[0,0]].
single rowLeft end seeds Pacific, right end seeds Atlantic; intersection where climbs overlap.
flat grid (all equal)`>=` lets water traverse everywhere; every cell reaches both oceans.

Pitfalls

Using `>` instead of `>=` — equal-height cells wrongly block the climb.
A single shared visited matrix for both oceans — a cell can belong to both sets.
Seeding only the corners instead of full border rows/columns — misses many reachable cells.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic 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++) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

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 col → Pacific
        dfs(heights, r, n - 1, atlantic);  // right col → Atlantic
    }
    for (int c = 0; c < n; c++) {
        dfs(heights, 0, c, pacific);       // top row → Pacific
        dfs(heights, m - 1, c, atlantic);  // bottom row → Atlantic
    }
    List<List<Integer>> res = new ArrayList<>();
    for (int r = 0; r < m; r++) {
        for (int c = 0; c < n; c++) {
            if (pacific[r][c] && atlantic[r][c]) {
                res.add(Arrays.asList(r, c));
            }
        }
    }
    return res;
}

private void dfs(int[][] h, int r, int c, boolean[][] ocean) {
    ocean[r][c] = true;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    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
                && !ocean[nr][nc] && h[nr][nc] >= h[r][c]) {
            dfs(h, nr, nc, ocean);
        }
    }
}

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong comparison operator (> vs >=)

Forward flow is allowed when neighbour ≤ current (equal allowed). In the reversed climb you must move to neighbours ≥ current, so the operator is >=; using > blocks valid equal-height paths.

Explore the code comparison

Don't write this

if heights[nr][nc] > heights[r][c]:  # blocks equal heights
    dfs(nr, nc, ocean)

Write this instead

if heights[nr][nc] >= heights[r][c]:  # equal heights pass
    dfs(nr, nc, ocean)

Shared visited set for both oceans

A cell can drain to both oceans, so it must be markable in both sets. One shared visited matrix would block the second ocean's traversal from re-marking it.

Explore the code comparison

Don't write this

boolean[][] visited = new boolean[m][n]; // shared
dfs(h, r, 0, visited);      // pacific
dfs(h, r, n-1, visited);    // atlantic blocked by pacific marks

Write this instead

boolean[][] pacific = new boolean[m][n];
boolean[][] atlantic = new boolean[m][n];
dfs(h, r, 0, pacific);
dfs(h, r, n-1, atlantic);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reverse multi-source DFS/BFS from both borders, then intersect

Code pattern to memorize

pacific  = cells reachable climbing from top+left borders
atlantic = cells reachable climbing from bottom+right borders
answer = [(r,c) for all cells if (r,c) in pacific and in atlantic]
# reverse rule: move to neighbour iff height[nb] >= height[cur]

Rules to remember

1Reverse the flow: water flows downhill, so to find what reaches an ocean, climb UPHILL from the ocean inward (neighbour ≥ current).
2Run two traversals: one seeded from Pacific borders (top row + left col), one from Atlantic borders (bottom row + right col).
3Use a visited set per ocean; the answer is the intersection of the two sets.
4Multi-source: seed the traversal with ALL border cells of that ocean at once, not one DFS per cell.
5The comparison is >= (not >) — equal-height neighbours still let water pass.

Use this pattern when

'Which cells can reach multiple targets/borders' on a grid
Reachability where simulating from each source is too expensive — reverse from the targets
Problems answered by intersecting two reachability sets
Border-seeded multi-source flood fill

Choose another pattern when

Single source/target → one ordinary BFS/DFS
Shortest distance needed → BFS with distance, not just reachability
Weighted heights with costs → Dijkstra, not flat flood fill

Interview takeaway

Pacific Atlantic teaches the 'reverse the search from the goal' trick: instead of asking 'can this cell reach an ocean?' n times, ask 'which cells can the ocean reach?' twice and intersect. The same reverse-multi-source idea solves Surrounded Regions and Walls and Gates.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternReverse multi-source flood fill from the targets, then intersect reachable sets. The key insight is searching backward from few targets instead of forward from many sources. Same family as Surrounded Regions and Walls and Gates.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Surrounded Regions
Reverse from the borders again: mark border-connected regions safe, flip the rest.
Number of Islands
Same grid flood-fill skeleton; count components instead of reverse-reachability.
Walls and Gates
Coming soon
Multi-source BFS from all gates at once — the distance version of multi-source seeding.
Rotting Oranges
Multi-source BFS counting minutes from all rotten oranges simultaneously.

Same pattern

←

Clone Graph

Continue · Next problem

Rotting Oranges

mediumGraphsLC #417Frequently asked

Pacific Atlantic Water Flow

LCPractice

Graphs · 4 of 34 · 10 min

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at (r, c).

Return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

In plain English

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]]
Note: These cells have a non-increasing path to both the Pacific (top/left) and Atlantic (bottom/right) borders.

Example 2

Input: heights = [[1]]
Output: [[0,0]]
Note: A single cell borders all four edges, so it trivially reaches both oceans.

Example 3

Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]
Note: Small grid where every cell can reach both oceans via the borders.

Constraints

m == heights.length
n == heights[r].length
1 ≤ m, n ≤ 200
0 ≤ heights[r][c] ≤ 10⁵

Clarifying questions4First question: Can water flow between equal-height cells?Explore questions

Q1.Can water flow between equal-height cells?
Yes — flow allowed when neighbour height ≤ current. So in the reversed climb, I move when neighbour ≥ current, using >= (equal heights pass).
Q2.Which edges touch which ocean?
Pacific = top row and left column; Atlantic = bottom row and right column. Corner cells border both.
Q3.Does the output order matter?
No — any order of the qualifying coordinates is accepted.
Q4.How big is the grid?
Up to 200×200 = 40,000 cells. The reverse approach is O(mn); the brute-force per-cell simulation would be ~O((mn)²) and too slow.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you avoid the O((mn)²) brute force by reversing the flow and seeding multi-source traversals from the borders, then intersecting two reachability sets.

Where candidates slip

Running a separate flow simulation from every cell (quadratic), using `>` instead of `>=`, or only seeding from corners instead of entire border rows/columns.

How to stand out

Explain the reversal insight crisply ('climb from the ocean'), seed both border sets, use a visited matrix per ocean, intersect, and note BFS works identically if recursion depth is a concern.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Flow Simulation From Every Cell	`O((m × n)²)`	`O(m × n)`	Mention to anchor why reversal is needed, then discard — it's quadratic in the number of cells.	Read
2	Reverse Multi-Source DFS From Both Oceans (Optimal)Optimal	`O(m × n)`	`O(m × n)`	The expected answer. Lead with the reversal: 'climb uphill from each ocean's border and intersect the two reachable sets'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Flow Simulation From Every Cell

TimeO((m × n)²)SpaceO(m × n)

Mention to anchor why reversal is needed, then discard — it's quadratic in the number of cells.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Literal reading: for each cell, can water flow downhill from it all the way to each ocean?

2Hint 2Explore hint

From each starting cell, DFS/BFS following non-increasing heights; record whether you reach a Pacific border and whether you reach an Atlantic border.

3Hint 3Explore hint

A cell qualifies if a single search from it touches both. But you'd repeat this search from all m·n cells — that's the bottleneck.

A · Core idea

Translate the problem directly: a cell drains to an ocean if a downhill (non-increasing) path leads from it to that ocean's edge.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

heights = [[2,1],[1,2]]

(0,0)=2

borders both Pacific(top/left); also can it reach Atlantic? downhill to (0,1)=1,(1,0)=1

Statereaches both

Final result[[0,0],[0,1],[1,0],[1,1]]

C · Code with teaching comments

solution.javaJava

Brute Force — Flow Simulation From Every Cell — reference

3 teaching notes

1
// Illustrative only — O((m*n)^2), too slow for the constraints.
2
public List<List<Integer>> pacificAtlantic(int[][] heights) {
3
    int m = heights.length, n = heights[0].length;
4
    List<List<Integer>> res = new ArrayList<>();
5
    for (int r = 0; r < m; r++) {
6
        for (int c = 0; c < n; c++) {
7
            // Track per-cell whether a downhill search hits each ocean.
8
            boolean[] reach = new boolean[2]; // [pacific, atlantic]
9
            boolean[][] seen = new boolean[m][n];
10
            // A full O(m·n) traversal per starting cell — the source of the quadratic
11
            // cost.
12
            flow(heights, r, c, seen, reach);
13
            if (reach[0] && reach[1]) {
14
                res.add(Arrays.asList(r, c));
15
            }
16
        }
17
    }
18
    return res;
19
}
20
// flow() DFS downhill, setting reach[] when a border is touched.

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.20 lines

D · Why it works and complexityO((m × n)²) timeO(m × n) spaceOpen the invariant and proofExplore the proof

ComplexityO((m × n)²) time, O(m × n) space — Each of the m·n cells launches a traversal that can visit up to m·n cells → O((m·n)²). The visited bookkeeping per search is O(m·n) space.

E · Edge cases and pitfalls3Re-running a full traversal per cell — quadratic and times out at 200×200.Explore edge cases

Pitfalls

Re-running a full traversal per cell — quadratic and times out at 200×200.
Resetting the visited structure incorrectly between cells.
Confusing flow direction (should be downhill, neighbour ≤ current, in the forward simulation).

03.2

Approach 2 of 2 · Optimal

Reverse Multi-Source DFS From Both Oceans (Optimal)

TimeO(m × n)SpaceO(m × n)

The expected answer. Lead with the reversal: 'climb uphill from each ocean's border and intersect the two reachable sets'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Flip the question. Instead of 'which cells reach the ocean?', ask 'which cells can the ocean reach if water flowed backward (uphill)?'

2Hint 2Explore hint

3Hint 3Explore hint

Any cell in both sets can drain to both oceans. Intersect the two visited sets for the answer.

A · Core idea

The whole problem cracks open once you reverse the flow.

Intersect. A cell that appears in both sets can drain to both oceans — that's the answer. Walk the grid once and collect cells present in both visited matrices.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

heights = [[1,2,2,3,5],[3,2,3,4,4],...] (5×5 sample)

Array state

pacific

reach from top/left

ocean ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final result[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

C · Code with teaching comments

solution.javaJava

Reverse Multi-Source DFS From Both Oceans (Optimal) — optimal

3 teaching notes

1
public List<List<Integer>> pacificAtlantic(int[][] heights) {
2
    int m = heights.length, n = heights[0].length;
3
    boolean[][] pacific = new boolean[m][n];
4
    boolean[][] atlantic = new boolean[m][n];
5
    for (int r = 0; r < m; r++) {
6
        dfs(heights, r, 0, pacific);       // left col → Pacific
7
        dfs(heights, r, n - 1, atlantic);  // right col → Atlantic
8
    }
9
    for (int c = 0; c < n; c++) {
10
        dfs(heights, 0, c, pacific);       // top row → Pacific
11
        dfs(heights, m - 1, c, atlantic);  // bottom row → Atlantic
12
    }
13
    List<List<Integer>> res = new ArrayList<>();
14
    for (int r = 0; r < m; r++) {
15
        for (int c = 0; c < n; c++) {
16
            if (pacific[r][c] && atlantic[r][c]) {
17
                res.add(Arrays.asList(r, c));
18
            }
19
        }
20
    }
21
    return res;
22
}
23
 
24
private void dfs(int[][] h, int r, int c, boolean[][] ocean) {
25
    ocean[r][c] = true;
26
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
27
    for (int[] d : dirs) {
28
        int nr = r + d[0], nc = c + d[1];
29
        if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length
30
                && !ocean[nr][nc] && h[nr][nc] >= h[r][c]) {
31
            dfs(h, nr, nc, ocean);
32
        }
33
    }
34
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.34 lines

D · Why it works and complexityO(m × n) timeO(m × n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls6single cell [[1]] — Borders all edges; in both sets → [[0,0]].Explore edge cases

Edge cases handled

single cell [[1]]Borders all edges; in both sets → [[0,0]].
single rowLeft end seeds Pacific, right end seeds Atlantic; intersection where climbs overlap.
flat grid (all equal)`>=` lets water traverse everywhere; every cell reaches both oceans.

Pitfalls

Using `>` instead of `>=` — equal-height cells wrongly block the climb.
A single shared visited matrix for both oceans — a cell can belong to both sets.
Seeding only the corners instead of full border rows/columns — misses many reachable cells.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Wrong comparison operator (> vs >=)

Forward flow is allowed when neighbour ≤ current (equal allowed). In the reversed climb you must move to neighbours ≥ current, so the operator is >=; using > blocks valid equal-height paths.

Explore the code comparison

Don't write this

if heights[nr][nc] > heights[r][c]:  # blocks equal heights
    dfs(nr, nc, ocean)

Write this instead

if heights[nr][nc] >= heights[r][c]:  # equal heights pass
    dfs(nr, nc, ocean)

Shared visited set for both oceans

A cell can drain to both oceans, so it must be markable in both sets. One shared visited matrix would block the second ocean's traversal from re-marking it.

Explore the code comparison

Don't write this

boolean[][] visited = new boolean[m][n]; // shared
dfs(h, r, 0, visited);      // pacific
dfs(h, r, n-1, visited);    // atlantic blocked by pacific marks

Write this instead

boolean[][] pacific = new boolean[m][n];
boolean[][] atlantic = new boolean[m][n];
dfs(h, r, 0, pacific);
dfs(h, r, n-1, atlantic);

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Reverse multi-source DFS/BFS from both borders, then intersect

Code pattern to memorize

pacific  = cells reachable climbing from top+left borders
atlantic = cells reachable climbing from bottom+right borders
answer = [(r,c) for all cells if (r,c) in pacific and in atlantic]
# reverse rule: move to neighbour iff height[nb] >= height[cur]

Rules to remember

1Reverse the flow: water flows downhill, so to find what reaches an ocean, climb UPHILL from the ocean inward (neighbour ≥ current).
2Run two traversals: one seeded from Pacific borders (top row + left col), one from Atlantic borders (bottom row + right col).
3Use a visited set per ocean; the answer is the intersection of the two sets.
4Multi-source: seed the traversal with ALL border cells of that ocean at once, not one DFS per cell.
5The comparison is >= (not >) — equal-height neighbours still let water pass.

Use this pattern when

'Which cells can reach multiple targets/borders' on a grid
Reachability where simulating from each source is too expensive — reverse from the targets
Problems answered by intersecting two reachability sets
Border-seeded multi-source flood fill

Choose another pattern when

Single source/target → one ordinary BFS/DFS
Shortest distance needed → BFS with distance, not just reachability
Weighted heights with costs → Dijkstra, not flat flood fill

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Surrounded Regions
Reverse from the borders again: mark border-connected regions safe, flip the rest.
Number of Islands
Same grid flood-fill skeleton; count components instead of reverse-reachability.
Walls and Gates
Coming soon
Multi-source BFS from all gates at once — the distance version of multi-source seeding.
Rotting Oranges
Multi-source BFS counting minutes from all rotten oranges simultaneously.

Same pattern

←

Clone Graph

Continue · Next problem

Rotting Oranges