Problem 22.6 · Depth-First SearchMedium

Pacific Atlantic Water Flow

PatternGraph DFS and Flood Fill Matrix Traversal

What it teaches: Two reverse searches from two borders, then intersect.

Practise it on judges as “Pacific Atlantic Water Flow”.

The problem

Water flows from a cell to a neighbour with equal or lower height. The Pacific touches the top and left edges, the Atlantic the bottom and right edges. Return all cells [r, c] from which water can reach both oceans (any order).

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

Constraints

1 ≤ rows, cols ≤ 200

Pattern clues in the wording

→ Which cells can reach a border
→ Two targets

These clues point to Graph DFS and Flood Fill: Go as deep as possible from a node, marking visited cells or nodes, to find connected regions.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	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]]	[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
2	heights = [[1]]	[[0,0]]

From slow to fast

Approaches

1. Reverse DFS from both oceans · O(rows × cols)

Reverse DFS from both oceans

Time O(rows × cols) Space O(rows × cols)

DFS from Pacific border cells to neighbours with height ≥ current; same for the Atlantic; collect cells marked by both.

Approach 1

import java.util.*;

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
        for (int r = 0; r < m; r++) { climb(heights, r, 0, pac); climb(heights, r, n - 1, atl); }
        for (int c = 0; c < n; c++) { climb(heights, 0, c, pac); climb(heights, m - 1, c, atl); }
        List<List<Integer>> out = new ArrayList<>();
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++)
                if (pac[r][c] && atl[r][c]) out.add(List.of(r, c));
        return out;
    }

    private void climb(int[][] h, int r, int c, boolean[][] seen) {
        if (seen[r][c]) return;
        seen[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 || nc < 0 || nr >= h.length || nc >= h[0].length) continue;
            if (h[nr][nc] >= h[r][c]) climb(h, nr, nc, seen);
        }
    }
}

Verdict: Each cell is visited at most twice.

Before you submit

Edge cases and common mistakes

Test these inputs

Single cell (touches both)
Flat grid (everything)

Mistakes people make

Simulating water downhill from every cell (O((mn)²)).

Interview

Follow-up questions

Could you use BFS instead?

Command Palette

The problem

Approaches

Reverse DFS from both oceans

Edge cases and common mistakes

Follow-up questions