Skip to main content

16. Pacific Atlantic Water Flow

mediumAsked at GitHub

Multi-source BFS/DFS on a grid to find cells reachable from both boundaries, testing bidirectional graph traversal skills GitHub values for diff and merge reachability.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m×n island height matrix, water can flow to adjacent cells of equal or lesser height. Find all cells that can flow to both the Pacific ocean (top/left border) and Atlantic ocean (bottom/right border).

Constraints

  • 1 <= m, n <= 200
  • 0 <= heights[i][j] <= 10^5

Examples

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

Example 2

Input
heights = [[1]]
Output
[[0,0]]

Approaches

1. Brute force: check each cell independently

For each cell run two DFS to see if it reaches both oceans — O(m²n²) total.

Time
O(m^2*n^2)
Space
O(m*n)
// For each cell, DFS for Pacific reachability then Atlantic
// Too slow for large grids

Tradeoff:

2. Reverse BFS from borders

Run BFS backwards from Pacific border cells and from Atlantic border cells (moving to equal-or-higher neighbors). Collect cells reachable from each ocean; return the intersection.

Time
O(m*n)
Space
O(m*n)
function pacificAtlantic(heights) {
  const m = heights.length, n = heights[0].length;
  const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
  function bfs(starts) {
    const visited = Array.from({length:m},()=>new Array(n).fill(false));
    const queue = [...starts];
    for (const [r,c] of starts) visited[r][c] = true;
    while (queue.length) {
      const [r,c] = queue.shift();
      for (const [dr,dc] of dirs) {
        const nr=r+dr, nc=c+dc;
        if (nr>=0&&nr<m&&nc>=0&&nc<n&&!visited[nr][nc]&&heights[nr][nc]>=heights[r][c]) {
          visited[nr][nc]=true;
          queue.push([nr,nc]);
        }
      }
    }
    return visited;
  }
  const pac=[], atl=[];
  for (let i=0;i<m;i++){pac.push([i,0]);atl.push([i,n-1]);}
  for (let j=0;j<n;j++){pac.push([0,j]);atl.push([m-1,j]);}
  const vP=bfs(pac), vA=bfs(atl);
  const res=[];
  for(let i=0;i<m;i++)for(let j=0;j<n;j++)if(vP[i][j]&&vA[i][j])res.push([i,j]);
  return res;
}

Tradeoff:

GitHub-specific tips

GitHub interviewers use this problem to probe reverse-traversal thinking — relate it to walking a dependency graph backwards from endpoints, similar to tracing which commits are reachable from both branch heads during a merge.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Pacific Atlantic Water Flow and other GitHub interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →