Pacific Atlantic Water Flow — Two-Source DFS

Problem

Water flows from higher/equal cells. Find all cells that can reach both Pacific (top/left border) and Atlantic (bottom/right border).

Approach — Reverse BFS/DFS from Borders

Instead of simulating forward flow (expensive), run DFS backwards from each ocean's border cells: a cell is reachable if its neighbor is ≥ it (reverse condition). Find cells reachable from both.

Time: O(mn) | Space: O(mn)

Solutions

Python

class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        R,C=len(heights),len(heights[0])
        def dfs(r,c,visited,prev):
            if not(0<=r<R and 0<=c<C) or (r,c) in visited or heights[r][c]<prev: return
            visited.add((r,c))
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                dfs(r+dr,c+dc,visited,heights[r][c])
        pac,atl=set(),set()
        for r in range(R):
            dfs(r,0,pac,heights[r][0]); dfs(r,C-1,atl,heights[r][C-1])
        for c in range(C):
            dfs(0,c,pac,heights[0][c]); dfs(R-1,c,atl,heights[R-1][c])
        return [[r,c] for r in range(R) for c in range(C) if (r,c) in pac and (r,c) in atl]

C++

class Solution {
    int R,C;
    void dfs(vector<vector<int>>& h, vector<vector<bool>>& vis, int r, int c, int prev){
        if(r<0||r>=R||c<0||c>=C||vis[r][c]||h[r][c]<prev) return;
        vis[r][c]=true;
        dfs(h,vis,r+1,c,h[r][c]); dfs(h,vis,r-1,c,h[r][c]);
        dfs(h,vis,r,c+1,h[r][c]); dfs(h,vis,r,c-1,h[r][c]);
    }
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& h){
        R=h.size(); C=h[0].size();
        vector<vector<bool>> pac(R,vector<bool>(C,false)), atl(R,vector<bool>(C,false));
        for(int r=0;r<R;r++){dfs(h,pac,r,0,0); dfs(h,atl,r,C-1,0);}
        for(int c=0;c<C;c++){dfs(h,pac,0,c,0); dfs(h,atl,R-1,c,0);}
        vector<vector<int>> res;
        for(int r=0;r<R;r++) for(int c=0;c<C;c++)
            if(pac[r][c]&&atl[r][c]) res.push_back({r,c});
        return res;
    }
};

Complexity

Time: O(mn) | Space: O(mn)