LeetCode · #417

Pacific Atlantic Water Flow Solution

Given a height matrix, find all cells from which water can flow to both the Pacific ocean (top/left border) and the Atlantic ocean (bottom/right border).

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #417

🏗️

Pattern

Graph — multi-source BFS reverse flow

There is an m × n island. The Pacific ocean borders the top and left, the Atlantic borders the bottom and right. Water flows from a cell to adjacent cells (4-directional) with height ≤ its own. Find all cells from which water can reach both oceans.

Example

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

Constraints

 • m == heights.length,  n == heights[i].length • 1 ≤ m, n ≤ 200  ← O(m·n) solution required • 0 ≤ heights[i][j] ≤ 10⁵ 

Section Two · Approach 1

Brute Force — DFS from Every Cell

For each cell, run two DFS searches: one checking if water can reach the Pacific, another for the Atlantic. For each DFS, flow is valid when moving to a neighbor with height ≤ current height. A cell is in the answer if both DFS calls succeed.

Why it works

The DFS correctly simulates water flow by only going to equal-or-lower cells. Running it from every cell and checking both oceans is correct but extremely slow.

Why we can do better

Problem: O(m · n) DFS per cell × O(m · n) cells = O(m² · n²) total. For a 200×200 grid that's 1.6 billion operations. The key insight is to reverse the direction: instead of flowing downhill from each cell, flow uphill from the ocean borders. This way, each cell is visited at most twice total — once from the Pacific BFS and once from the Atlantic BFS.

Java — Brute force DFS from each cell

 import java.util.*;
class Solution {
int m, n;
int[][] h;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
        m = heights.length; n = heights[0].length; h = heights;
List<List<Integer>> res = new ArrayList<>();
for (int r=0; r<m; r++) for (int c=0; c<n; c++)
if (canReach(r,c,true) && canReach(r,c,false))
                res.add(Arrays.asList(r,c));
return res;
    }
private boolean canReach(int r, int c, boolean pacific) {
boolean[][] vis = new boolean[m][n];
return dfs(r, c, vis, pacific);
    }
private boolean dfs(int r, int c, boolean[][] vis, boolean pacific) {
if (pacific && (r==0||c==0)) return true;
if (!pacific && (r==m-1||c==n-1)) return true;
        vis[r][c] = true;
for (int[] d : new int[][]{{1,0},{-1,0},{0,1},{0,-1}}) {
int nr=r+d[0], nc=c+d[1];
if (nr>=0&&nr<m&&nc>=0&&nc<n&&!vis[nr][nc]&&h[nr][nc]<=h[r][c])
if (dfs(nr,nc,vis,pacific)) return true;
        }
return false;
    }
}

Python — Brute force DFS from each cell

 class Solution:
def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        m, n = len(heights), len(heights[0])
def can_reach(r, c, pacific):
            vis = set()
def dfs(r, c):
if pacific and (r==0 or c==0): return True if not pacific and (r==m-1 or c==n-1): return True
vis.add((r,c))
for dr,dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                    nr,nc = r+dr,c+dc
if 0<=nr<m and 0<=nc<n and (nr,nc) not in vis and heights[nr][nc]<=heights[r][c]:
if dfs(nr,nc): return True return False return dfs(r, c)
return [[r,c] for r in range(m) for c in range(n)
if can_reach(r,c,True) and can_reach(r,c,False)]

Metric	Value
Time	O(m² · n²) — O(m·n) DFS per cell
Space	O(m · n) — visited set per DFS call

Section Three · Approach 2

Multi-Source BFS Reverse Flow — O(m·n)

Instead of flowing downhill from each cell, run two BFS/DFS searches flowing uphill from the ocean borders. Pacific BFS starts from all top-row and left-column cells. Atlantic BFS starts from all bottom-row and right-column cells. The answer is the intersection of cells reachable by both.

💡 Mental model: You're a rain cloud trying to grow a river network. Instead of asking "can water from this mountain top reach the sea?", you're asking "how far inland can the sea send a tidal wave if water could flow uphill?" Start all the Pacific coastline cells in your BFS frontier simultaneously. Expand inland only to cells that are equal-or-higher (uphill). The cells you can reach = cells whose water can flow back down to the Pacific. Do the same for the Atlantic. The cells reachable from both coastlines are your answer.

Algorithm — two multi-source BFS passes

Pacific BFS: seed with all top-row + left-column cells. Expand to neighbors with height ≥ current (reverse flow = going uphill).
Atlantic BFS: seed with all bottom-row + right-column cells. Same expansion rule.
Result: all (r, c) where pacific[r][c] && atlantic[r][c].

🎯 When to recognize this pattern:

Any problem asking "cells reachable from multiple border regions simultaneously." The key is reversing the flow direction to turn a per-cell O(m·n) search into two O(m·n) multi-source BFS passes.
Similar problems: LC 1020 (Number of Enclaves — cells NOT reachable from border), LC 130 (Surrounded Regions — flip cells not reachable from border).

Why seeding both borders simultaneously works:

BFS treats all initial seeds as if they started at "distance 0." By seeding the entire coastline at once, we compute "can-reach-ocean" for every cell in one pass rather than one DFS per cell.
The height comparison (≥ current) ensures we only expand to cells whose water could flow back to the current cell (i.e., cells the current cell can drain to).

Section Four · Trace

Visual Walkthrough

Simplified 4×4 trace showing Pacific-reachable (blue), Atlantic-reachable (orange), and intersection (green).

Multi-Source BFS — Pacific ∩ Atlantic = answer cells

Section Five · Implementation

Code — Java & Python

Java — Multi-source BFS

 import java.util.*;
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public List<List<Integer>> pacificAtlantic(int[][] h) {
int m = h.length, n = h[0].length;
boolean[][] pac = new boolean[m][n];
boolean[][] atl = new boolean[m][n];
Queue<int[]> pq = new LinkedList<>();
Queue<int[]> aq = new LinkedList<>();
for (int r = 0; r < m; r++) {
seed(pq, pac, r, 0); // left column → Pacific seed(aq, atl, r, n-1); // right column → Atlantic
}
for (int c = 0; c < n; c++) {
seed(pq, pac, 0, c); // top row → Pacific seed(aq, atl, m-1, c); // bottom row → Atlantic
}
bfs(h, pq, pac);
bfs(h, aq, atl);
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;
    }
private void seed(Queue<int[]> q, boolean[][] vis, int r, int c) {
if (!vis[r][c]) { vis[r][c] = true; q.offer(new int[]{r,c}); }
    }
private void bfs(int[][] h, Queue<int[]> q, boolean[][] vis) {
int m = h.length, n = h[0].length;
while (!q.isEmpty()) {
int[] cell = q.poll();
for (int[] d : DIRS) {
int nr = cell[0]+d[0], nc = cell[1]+d[1];
if (nr>=0&&nr<m&&nc>=0&&nc<n&&!vis[nr][nc]
                        && h[nr][nc]>=h[cell[0]][cell[1]]) { // reverse: uphill
vis[nr][nc] = true;
                    q.offer(new int[]{nr, nc});
                }
            }
        }
    }
}

Python — Multi-source BFS

 from collections import deque
class Solution:
def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        m, n = len(heights), len(heights[0])
def bfs(seeds):
            vis = set(seeds)
            q = deque(seeds)
while q:
                r, c = q.popleft()
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                    nr, nc = r+dr, c+dc
if (0<=nr<m and 0<=nc<n and
(nr,nc) not in vis and
heights[nr][nc] >= heights[r][c]): # reverse: uphill
vis.add((nr,nc))
                        q.append((nr,nc))
return vis

        pac_seeds = [(r,0) for r in range(m)] + [(0,c) for c in range(n)]
        atl_seeds = [(r,n-1) for r in range(m)] + [(m-1,c) for c in range(n)]

        pac = bfs(pac_seeds)
        atl = bfs(atl_seeds)
return [[r,c] for r,c in pac & atl]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Brute force DFS per cell	O(m² · n²)	O(m · n)	TLE for 200×200 grid
Memoized DFS per cell	O(m · n)	O(m · n)	Complex to implement correctly with dual-ocean memoization
Multi-source BFS ← optimal	O(m · n)	O(m · n)	Two clean BFS passes; simple set intersection for answer

Why reverse flow is the core insight:

Forward flow (downhill from each cell) requires a fresh DFS per cell — O(m·n · m·n).
Reverse flow (uphill from ocean borders) shares work across all cells because all border cells are in the same BFS frontier.
Each cell is visited at most once per ocean BFS — total O(m·n).

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
1×1 grid	`[[5]]`	Single cell borders both oceans simultaneously. Result: `[[0,0]]`.
All same height	All equal heights	Every cell can flow everywhere — entire grid is the answer.
Monotone increasing top-left → bottom-right	Heights increase	Corner cells border both oceans. BFS propagates through all equal/higher cells.
Tall ridge in the middle	High center row	Ridge cells border both oceans (seeded in both BFS). Cells on each side only reach one ocean.
Duplicate border seeds	Corner cells appear in both row and column seeds	Corner cells like `(0,0)` appear in both row-0 and col-0 seeds. The `visited` check prevents double-enqueuing.
Wrong height comparison direction	any	Using `<=` instead of `>=` in the BFS expansion gives forward flow (water flowing downhill from ocean) instead of reverse. This would be nonsensical — the result would be empty.

⚠ Common Mistake: Using heights[nr][nc] <= heights[r][c] in the BFS instead of >=. Since we're doing reverse flow (flowing uphill from the ocean), we can only move to cells that are at least as high as the current one — i.e., cells whose water could have flowed down to us. Using <= would model forward flow from the ocean, which is physically meaningless and produces a wrong answer.

← Back to Graph problems

LearningTree

LC 417 · Pacific Atlantic Water Flow — Solution & Explanation | DSA Guide