#417 Pacific Atlantic Water Flow

frequently reported atAmazon Google

the problem

In plain words

heights is an island. The Pacific touches the top and left edges; the Atlantic the bottom and right. Water flows to a neighbour with height ≤ the current one. Return every cell from which water can reach both oceans.

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

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

in heights = [[1]]

out [[0,0]]

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

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternReverse search from the border Multi-source BFS

Asking "where can water from this cell go?" for every cell is slow. Ask the reverse: "which cells can the ocean climb up to?" Two searches, one per ocean, then intersect.

solutions

From brute force to optimal

For each cell, DFS to lower-or-equal neighbours and record which edges it touches.

For each cell, run a fresh DFS with its own visited array.
Touching row 0 / col 0 → Pacific; last row / last col → Atlantic.
Keep cells that reach both.

timeO((m · n)²)

m·n searches, each up to m·n cells.

spaceO(m · n)

Visited array and recursion for one search.

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};3 4    /** From every cell, flood "downhill" and see which oceans the water can reach. */5    public List<List<Integer>> pacificAtlantic(int[][] heights) {6        int rows = heights.length, cols = heights[0].length;7        List<List<Integer>> result = new ArrayList<>();8        for (int r = 0; r < rows; r++)9            for (int c = 0; c < cols; c++) {10                boolean[] oceans = new boolean[2]; // [0] = Pacific, [1] = Atlantic11                flow(heights, r, c, new boolean[rows][cols], oceans);12                if (oceans[0] && oceans[1]) result.add(List.of(r, c));13            }14        return result;15    }16 17    private void flow(int[][] h, int r, int c, boolean[][] seen, boolean[] oceans) {18        seen[r][c] = true;19        if (r == 0 || c == 0) oceans[0] = true;                         // top or left edge20        if (r == h.length - 1 || c == h[0].length - 1) oceans[1] = true; // bottom or right edge21        for (int[] d : DIRS) {22            int nr = r + d[0], nc = c + d[1];23            if (nr < 0 || nc < 0 || nr >= h.length || nc >= h[0].length || seen[nr][nc]) continue;24            if (h[nr][nc] <= h[r][c]) flow(h, nr, nc, seen, oceans); // water runs to lower or equal25        }26    }27}

Multi-source DFS from each ocean's border cells, moving only to higher-or-equal neighbours.

DFS from every Pacific border cell into pacific[][].
DFS from every Atlantic border cell into atlantic[][].
Answer = cells marked in both.

timeO(m · n)

Each cell is marked at most once per ocean.

spaceO(m · n)

Two boolean grids plus recursion depth.

javajava.util.*

1class Solution {2    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};3 4    /** Reverse the flow: climb UP from each ocean's shore; answer = cells both oceans can climb to. */5    public List<List<Integer>> pacificAtlantic(int[][] heights) {6        int rows = heights.length, cols = heights[0].length;7        boolean[][] pacific = new boolean[rows][cols], atlantic = new boolean[rows][cols];8        for (int r = 0; r < rows; r++) {9            climb(heights, r, 0, pacific);10            climb(heights, r, cols - 1, atlantic);11        }12        for (int c = 0; c < cols; c++) {13            climb(heights, 0, c, pacific);14            climb(heights, rows - 1, c, atlantic);15        }16        List<List<Integer>> result = new ArrayList<>();17        for (int r = 0; r < rows; r++)18            for (int c = 0; c < cols; c++)19                if (pacific[r][c] && atlantic[r][c]) result.add(List.of(r, c));20        return result;21    }22 23    private void climb(int[][] h, int r, int c, boolean[][] reach) {24        if (reach[r][c]) return;25        reach[r][c] = true;26        for (int[] d : DIRS) {27            int nr = r + d[0], nc = c + d[1];28            if (nr < 0 || nc < 0 || nr >= h.length || nc >= h[0].length) continue;29            if (h[nr][nc] >= h[r][c]) climb(h, nr, nc, reach); // uphill or flat only30        }31    }32}

in the room

How to say it in the interview

talk track

Lead with the reversal: "water flows down from a cell ⇔ the ocean can climb up to that cell."

traps

Flipping the comparison the wrong way when reversing: going up means h[next] >= h[cur].
Forgetting that equal heights let water flow.

what they ask next

Follow-ups

The grid is 10⁴ × 10⁴ — will the recursive climb survive?

Not in Java: a flat region makes the recursion as deep as the region. Run the same climb as a multi-source BFS — seed the queue with every shore cell of one ocean.

before you submit

Edge cases to test

A single cell touches both oceans → [[0,0]].
A flat grid: every cell reaches both oceans.
A pit lower than all its neighbours drains nowhere — unless it is on the shore.

practise next