Pacific Atlantic Water Flow

mediumGraphs: BFS / DFS421 stepsJava · Python · C++

Find cells whose water can flow to both oceans (water flows to equal or lower neighbours). Flip the direction: from each ocean's border, climb to equal or higher neighbours to find everything that drains into it. The answer is the overlap.

▶ Watch the animated trace

Traced input: heights = [[1, 2, 2, 3], [3, 2, 3, 4], [2, 4, 5, 3], [6, 7, 1, 4]] → [[0, 3], [1, 3], [2, 2], [3, 0], [3, 1]]. Original problem: neetcode.io/problems/pacific-atlantic-water-flow

Complexity

BestO(m·n)

AverageO(m·n)

WorstO(m·n)

SpaceO(m·n)

Two traversals, each visiting every cell at most once.

Key idea

Searching from every cell is O((m·n)²); searching backwards from the oceans is linear.
Pacific touches the top and left edges; Atlantic the bottom and right.
Reverse flow: move to a neighbour only if it's at least as high.
Cells reachable from both searches are the answer.

Common mistakes

Using < instead of <=: equal heights let water flow.
Mixing up which edges belong to which ocean.

Solution

Java

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
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, pac, r, 0);
        climb(heights, atl, r, n - 1);
    }
    for (int c = 0; c < n; c++) {
        climb(heights, pac, 0, c);
        climb(heights, atl, m - 1, c);
    }
    List<List<Integer>> res = new ArrayList<>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (pac[r][c] && atl[r][c]) res.add(Arrays.asList(r, c));
    return res;
}

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

Python

# DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]: down, up, right, left
def pacificAtlantic(heights: List[List[int]]) -> List[List[int]]:
    m, n = len(heights), len(heights[0])
    pac, atl = set(), set()

    def climb(r: int, c: int, seen: set) -> None:
        if (r, c) in seen: return
        seen.add((r, c))
        for dr, dc in DIRS:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and heights[nr][nc] >= heights[r][c]: climb(nr, nc, seen)

    for r in range(m):
        climb(r, 0, pac)
        climb(r, n - 1, atl)
    for c in range(n):
        climb(0, c, pac)
        climb(m - 1, c, atl)
    return [[r, c] for r in range(m) for c in range(n) if (r, c) in pac and (r, c) in atl]

C++

// DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}: down, up, right, left
void climb(vector<vector<int>>& h, vector<vector<bool>>& seen, int r, int c) {
    if (seen[r][c]) return;
    seen[r][c] = true;
    for (auto& d : DIRS) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nc >= 0 && nr < (int)h.size() && nc < (int)h[0].size() && h[nr][nc] >= h[r][c]) climb(h, seen, nr, nc);
    }
}

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int m = heights.size(), n = heights[0].size();
    vector<vector<bool>> pac(m, vector<bool>(n)), atl(m, vector<bool>(n));
    for (int r = 0; r < m; r++) {
        climb(heights, pac, r, 0);
        climb(heights, atl, r, n - 1);
    }
    for (int c = 0; c < n; c++) {
        climb(heights, pac, 0, c);
        climb(heights, atl, m - 1, c);
    }
    vector<vector<int>> res;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (pac[r][c] && atl[r][c]) res.push_back({r, c});
    return res;
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single cell It touches both oceans.	`heights = [[1]]`	`[[0, 0]]`
Flat grid Equal heights flow everywhere.	`heights = [[1, 1], [1, 1]]`	`[[0, 0], [0, 1], [1, 0], [1, 1]]`
Single row Every cell touches the top (Pacific) and bottom (Atlantic) edges.	`heights = [[3, 1, 2]]`	`[[0, 0], [0, 1], [0, 2]]`