Pacific Atlantic Water Flow

Medium · Graphs · Explanation and code example

Breadth First Search

How it works

Do the same “reverse flow” idea, but with BFS.

A cell can flow to an ocean if you can start from the ocean border and move backwards into the grid using the rule:

from (r, c) you can go to neighbor (nr, nc) if heights[nr][nc] >= heights[r][c] (because in the real direction water would flow from higher/equal down to (r, c)).

So:

Multi-source BFS from all Pacific border cells marks pac[r][c] = True
Multi-source BFS from all Atlantic border cells marks atl[r][c] = True Cells that are True in both are the answer.

Steps

Create two boolean grids pac and atl (same size as heights), all false.
Build two source lists:
- pacificSources: all cells on top row + left column
- atlanticSources: all cells on bottom row + right column
Run BFS(sources, oceanGrid):
- Initialize queue with all sources.
- While queue not empty:
  - pop (r, c), mark oceanGrid[r][c] = true
  - for each neighbor (nr, nc) in 4 directions:
    - if inside grid AND not visited in oceanGrid AND heights[nr][nc] >= heights[r][c], push (nr, nc) into queue.
Run BFS for Pacific → fill pac.
Run BFS for Atlantic → fill atl.
Iterate all cells; if pac[r][c] and atl[r][c] are both true, add [r, c] to result.
Return result.

Complexity

Time complexity: O(m * n)
Space complexity: O(m * n)

Where m is the number of rows and n is the number of columns.

Things to watch for

Using the Wrong Flow Direction Comparison

When starting from ocean borders and moving inward, the comparison must check if the neighbor height is greater than or equal to the current height (water flows uphill in reverse). Using the normal downhill comparison (neighbor <= current) gives incorrect reachability since the logic is reversed.

Running Separate DFS/BFS for Each Cell

A brute force approach that runs a full traversal from every cell to check ocean reachability leads to O((m*n)^2) time complexity or worse. The efficient approach is to run only two traversals total: one multi-source search from all Pacific border cells and one from all Atlantic border cells.

Not Properly Handling Edge and Corner Cells

Edge cells border one ocean while corner cells border both oceans. A common bug is forgetting that cells on the top row and left column touch the Pacific, while cells on the bottom row and right column touch the Atlantic. Missing any border initialization causes incomplete reachability sets.

Python code example

from typing import List
from collections import deque

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        ROWS, COLS = len(heights), len(heights[0])
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        pac = [[False] * COLS for _ in range(ROWS)]
        atl = [[False] * COLS for _ in range(ROWS)]

        def bfs(source, ocean):
            q = deque(source)
            while q:
                r, c = q.popleft()
                ocean[r][c] = True
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < ROWS and 0 <= nc < COLS and
                        not ocean[nr][nc] and
                        heights[nr][nc] >= heights[r][c]
                    ):
                        q.append((nr, nc))

        pacific = []
        atlantic = []
        for c in range(COLS):
            pacific.append((0, c))
            atlantic.append((ROWS - 1, c))

        for r in range(ROWS):
            pacific.append((r, 0))
            atlantic.append((r, COLS - 1))

        bfs(pacific, pac)
        bfs(atlantic, atl)

        res = []
        for r in range(ROWS):
            for c in range(COLS):
                if pac[r][c] and atl[r][c]:
                    res.append([r, c])
        return res

C++ code example

class Solution {
    vector<pair<int, int>> directions = {{1, 0}, {-1, 0},
                                         {0, 1}, {0, -1}};
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int ROWS = heights.size(), COLS = heights[0].size();
        vector<vector<bool>> pac(ROWS, vector<bool>(COLS, false));
        vector<vector<bool>> atl(ROWS, vector<bool>(COLS, false));

        queue<pair<int, int>> pacQueue, atlQueue;

        for (int c = 0; c < COLS; ++c) {
            pacQueue.push({0, c});
            atlQueue.push({ROWS - 1, c});
        }
        for (int r = 0; r < ROWS; ++r) {
            pacQueue.push({r, 0});
            atlQueue.push({r, COLS - 1});
        }

        bfs(pacQueue, pac, heights);
        bfs(atlQueue, atl, heights);

        vector<vector<int>> res;
        for (int r = 0; r < ROWS; ++r) {
            for (int c = 0; c < COLS; ++c) {
                if (pac[r][c] && atl[r][c]) {
                    res.push_back({r, c});
                }
            }
        }
        return res;
    }

private:
    void bfs(queue<pair<int, int>>& q, vector<vector<bool>>& ocean,
                                        vector<vector<int>>& heights) {
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            ocean[r][c] = true;
            for (auto [dr, dc] : directions) {
                int nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < heights.size() && nc >= 0 &&
                    nc < heights[0].size() && !ocean[nr][nc] &&
                    heights[nr][nc] >= heights[r][c]) {
                    q.push({nr, nc});
                }
            }
        }
    }
};

Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations