Blind 75 Visualized

#46 · Graphs

Pacific Atlantic Water Flow

Given a grid of heights, rain water flows to a neighbouring cell with equal or lower height. The Pacific touches the top and left edges and the Atlantic touches the bottom and right edges. Return every cell from which water can flow to both oceans.

MediumLeetCode
  • Computing
  • Depends on
  • Answer
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Reverse search from the sources

Instead of asking from each cell "where does the water go?", start at each ocean and walk uphill: a cell is reachable if it is at least as high as the cell you came from. The set of cells reached from one ocean is exactly the set of cells that drain into it.

Memory layout

One boolean (or one bit) per cell per ocean, plus a stack or queue for the search.

OperationCost
timeO(m·n): each cell is entered once per ocean
spaceO(m·n)

Bit flags per cell

Pack both oceans into one byte: bit 1 for the Pacific, bit 2 for the Atlantic. A single array replaces two grids, and "both" is just the value 3.

Memory layout

A flat byte array of m·n cells, indexed by row × cols + col.

OperationCost
test / set a bitO(1)

Why it fits

  • Forward simulation from every cell repeats the same downhill floods again and again. Starting from the oceans shares the work: one flood per ocean covers every cell.
  • The uphill walk is the exact reverse of the downhill flow rule, so the cells it reaches are precisely the cells that could flow to that ocean.
  • Intersecting two reach sets is a single scan, so the total work is a constant number of passes over the grid.

Why alternatives degrade

Flood from every cell:
Each flood can touch the whole grid, giving O((m·n)²) work.
Sorting cells by height:
Height alone does not tell you whether a path of non-increasing heights exists; connectivity matters.
One search from both oceans at once:
It cannot tell which ocean a cell reached, so it cannot compute the intersection.

Four approaches, from naive to production

1 · beginner

Flood downhill from every cell

time O((m·n)²)space O(m·n)

For every cell run a flood that moves to neighbours of equal or lower height, noting whether it touches a Pacific edge and an Atlantic edge. Keep the cells where both are true.

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int rows = heights.size(), cols = heights[0].size();
    auto flows = [&](int sr, int sc) -> bool {
        bool pacific = false, atlantic = false;
        set<int> seen = {sr * cols + sc};
        vector<pair<int, int>> stack = {{sr, sc}};
        while (!stack.empty()) {
            auto [r, c] = stack.back(); stack.pop_back();
            if (r == 0 || c == 0) pacific = true;
            if (r == rows - 1 || c == cols - 1) atlantic = true;
            int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                if (heights[nr][nc] > heights[r][c] || seen.count(nr * cols + nc)) continue;
                seen.insert(nr * cols + nc);
                stack.push_back({nr, nc});
            }
        }
        return pacific && atlantic;
    };
    vector<vector<int>> result;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (flows(r, c)) result.push_back({r, c});
        }
    }
    return result;
}

Flaws & bottlenecks

  • Every cell triggers its own flood, and most floods overlap heavily with their neighbours.
  • The same cells are revisited up to m·n times in total.
  • It builds a new visited set for every start cell.

Interviewer cross-questions

What is the complexity?

Say: There are m·n start cells and each flood can visit up to m·n cells, so O((m·n)²) in the worst case.

How do you notice the wasted work?

Say: A cell that drains to the Pacific makes all higher neighbours drain there too, yet each of them re-discovers it from scratch.

How can the work be shared?

Say: Reverse the direction: start at the ocean and climb uphill, so one search covers every cell for that ocean.

2 · intermediate

Two BFS from the oceans, climbing uphill

time O(m·n)space O(m·n)

Queue every cell on the Pacific edge and run a breadth-first search that moves to neighbours at least as high as the current cell. Do the same for the Atlantic. The answer is the cells reached by both searches.

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int rows = heights.size(), cols = heights[0].size();
    int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    auto bfs = [&](const vector<pair<int, int>>& starts) {
        vector<vector<bool>> reach(rows, vector<bool>(cols, false));
        vector<pair<int, int>> queue;
        for (auto [r, c] : starts) {
            reach[r][c] = true;
            queue.push_back({r, c});
        }
        size_t head = 0;
        while (head < queue.size()) {
            auto [r, c] = queue[head++];
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                if (reach[nr][nc] || heights[nr][nc] < heights[r][c]) continue;
                reach[nr][nc] = true;
                queue.push_back({nr, nc});
            }
        }
        return reach;
    };
    vector<pair<int, int>> pacificStarts, atlanticStarts;
    for (int r = 0; r < rows; r++) {
        pacificStarts.push_back({r, 0});
        atlanticStarts.push_back({r, cols - 1});
    }
    for (int c = 0; c < cols; c++) {
        pacificStarts.push_back({0, c});
        atlanticStarts.push_back({rows - 1, c});
    }
    auto pacific = bfs(pacificStarts), atlantic = bfs(atlanticStarts);
    vector<vector<int>> result;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (pacific[r][c] && atlantic[r][c]) result.push_back({r, c});
        }
    }
    return result;
}

Flaws & bottlenecks

  • Needs two full boolean matrices plus a queue.
  • The BFS helper repeats the same neighbour logic as its DFS cousin; the code is long.
  • Using shift() on a plain array for the queue can be slow, which is why this version uses a head index.

Interviewer cross-questions

Why climb uphill?

Say: Water flows from high to low, so if water can go from B down to A, then B is at least as high as A. Walking from the ocean to cells that are at least as high is that flow in reverse.

Why do the border cells start as reached?

Say: Water on an edge cell flows straight off the grid into the ocean next to it, regardless of its height.

BFS or DFS?

Say: Either works and visits each cell once per ocean. BFS uses a queue and has no recursion limit; DFS recursion is shorter but can go as deep as m·n.

3 · advanced

Two recursive DFS from the border

time O(m·n)space O(m·n) including recursion

Same reverse search written recursively: dfs(r, c, reach, prev) stops if the cell is off-grid, already reached, or lower than the previous cell, otherwise marks it and recurses into all four neighbours. Run it from every edge cell for each ocean.

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int rows = heights.size(), cols = heights[0].size();
    vector<vector<bool>> pacific(rows, vector<bool>(cols, false));
    vector<vector<bool>> atlantic(rows, vector<bool>(cols, false));
    function<void(int, int, vector<vector<bool>>&, int)> dfs = [&](int r, int c, vector<vector<bool>>& reach, int prev) {
        if (r < 0 || c < 0 || r >= rows || c >= cols) return;
        if (reach[r][c] || heights[r][c] < prev) return;
        reach[r][c] = true;
        dfs(r + 1, c, reach, heights[r][c]);
        dfs(r - 1, c, reach, heights[r][c]);
        dfs(r, c + 1, reach, heights[r][c]);
        dfs(r, c - 1, reach, heights[r][c]);
    };
    for (int r = 0; r < rows; r++) {
        dfs(r, 0, pacific, 0);
        dfs(r, cols - 1, atlantic, 0);
    }
    for (int c = 0; c < cols; c++) {
        dfs(0, c, pacific, 0);
        dfs(rows - 1, c, atlantic, 0);
    }
    vector<vector<int>> result;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (pacific[r][c] && atlantic[r][c]) result.push_back({r, c});
        }
    }
    return result;
}

Flaws & bottlenecks

  • Recursion depth can reach m·n on a spiral-shaped ridge, risking stack overflow.
  • Every cell makes four calls even when most return immediately.
  • Passing the previous height around is easy to get wrong (comparing with the wrong cell breaks the rule).

Interviewer cross-questions

Why pass prev as 0 at the border?

Say: Any real height is at least 0, so the first check always passes for border cells. Border cells are reached unconditionally.

Why can a cell be reached from the other ocean as well?

Say: The two searches use separate boolean grids. A cell can be marked in both, and those cells are the answer.

How would you remove recursion?

Say: Replace the call stack with an explicit stack of cells, as the expert approach does.

4 · expert

Bit flags + explicit stack

time O(m·n)space O(m·n)

Use one byte array and a bit per ocean. An iterative fill pops a cell, and for each in-bounds neighbour that lacks the bit and is at least as high, sets the bit and pushes it. The answer is the cells whose flags equal 3.

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int rows = heights.size(), cols = heights[0].size();
    vector<unsigned char> flags(rows * cols, 0);
    auto fill = [&](const vector<int>& starts, int bit) {
        vector<int> stack;
        for (int s : starts) {
            flags[s] |= bit;
            stack.push_back(s);
        }
        while (!stack.empty()) {
            int cell = stack.back(); stack.pop_back();
            int r = cell / cols, c = cell % cols;
            int h = heights[r][c];
            if (r > 0 && !(flags[cell - cols] & bit) && heights[r - 1][c] >= h) {
                flags[cell - cols] |= bit;
                stack.push_back(cell - cols);
            }
            if (r + 1 < rows && !(flags[cell + cols] & bit) && heights[r + 1][c] >= h) {
                flags[cell + cols] |= bit;
                stack.push_back(cell + cols);
            }
            if (c > 0 && !(flags[cell - 1] & bit) && heights[r][c - 1] >= h) {
                flags[cell - 1] |= bit;
                stack.push_back(cell - 1);
            }
            if (c + 1 < cols && !(flags[cell + 1] & bit) && heights[r][c + 1] >= h) {
                flags[cell + 1] |= bit;
                stack.push_back(cell + 1);
            }
        }
    };
    vector<int> pacific, atlantic;
    for (int r = 0; r < rows; r++) {
        pacific.push_back(r * cols);
        atlantic.push_back(r * cols + cols - 1);
    }
    for (int c = 0; c < cols; c++) {
        pacific.push_back(c);
        atlantic.push_back((rows - 1) * cols + c);
    }
    fill(pacific, 1);
    fill(atlantic, 2);
    vector<vector<int>> result;
    for (int i = 0; i < rows * cols; i++) {
        if (flags[i] == 3) result.push_back({i / cols, i % cols});
    }
    return result;
}

Flaws & bottlenecks

  • The four near-identical direction blocks are verbose; a direction table would be shorter but adds indirection.
  • Index arithmetic (cell − cols, cell + 1) hides the row and column and is easy to mistype.
  • It assumes each ocean search runs to completion before the next (otherwise the flag logic still works, but the code is harder to read).

Interviewer cross-questions

Why a bit per ocean?

Say: It halves the memory traffic (one byte instead of two booleans) and "reaches both" becomes a single comparison with 3.

Why an explicit stack?

Say: It avoids deep recursion on large grids and removes the cost of call frames. The visiting order is irrelevant here because we only need reachability.

Can both searches share one pass?

Say: They can run interleaved with different bits on the same array, but each search needs its own frontier. Running them one after another is simpler and just as fast.

Synchronized code walkthrough

Showing: Flood downhill from every cell — shares the player above; click any step to jump.

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int rows = heights.size(), cols = heights[0].size();
    auto flows = [&](int sr, int sc) -> bool {
        bool pacific = false, atlantic = false;
        set<int> seen = {sr * cols + sc};
        vector<pair<int, int>> stack = {{sr, sc}};
        while (!stack.empty()) {
            auto [r, c] = stack.back(); stack.pop_back();
            if (r == 0 || c == 0) pacific = true;
            if (r == rows - 1 || c == cols - 1) atlantic = true;
            int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
                if (heights[nr][nc] > heights[r][c] || seen.count(nr * cols + nc)) continue;
                seen.insert(nr * cols + nc);
                stack.push_back({nr, nc});
            }
        }
        return pacific && atlantic;
    };
    vector<vector<int>> result;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (flows(r, c)) result.push_back({r, c});
        }
    }
    return result;
}