Definition
- Pacific Atlantic Water Flow – find all cells in a height grid from which water can drain to both the Pacific (top and left edges) and the Atlantic (bottom and right edges).
- Flow reversal – instead of searching outward from every cell, reverse the direction and search inward from each ocean's border, moving only to neighbors of equal or greater height.
- Two reachability sets – one boolean matrix per ocean marks which cells that ocean can reach; the answer is their intersection.
- Linear time – each cell is visited at most twice (once per ocean), giving O(rows x cols) time.
- Linear space – the two boolean matrices use O(rows x cols) extra space.
Imagine a terrain of account-balance heights at the National Bank of India, where funds drain downhill to two settlement pools. The Pacific pool touches the top and left edges, and the Atlantic pool touches the bottom and right edges. Instead of testing every cell to see if it drains to both pools, Rajesh starts at each pool's edge and climbs uphill, marking every cell that could drain into that pool. Cells marked by both climbs are the ones that feed both pools.
Understanding the Concepts
What is the Pacific Atlantic Water Flow problem?
You are given an m x n grid of cell heights. Water flows from a cell to any of its four neighbors with equal or lower height. The Pacific Ocean borders the top row and left column. The Atlantic Ocean borders the bottom row and right column. You must return all cells from which water can reach both oceans.
package com.bank.service;
import java.util.*;
public class PacificAtlanticFlow {
private static final int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};
public List<int[]> pacificAtlantic(int[][] heights) {
int rows = heights.length, cols = heights[0].length;
boolean[][] pacific = new boolean[rows][cols];
boolean[][] atlantic = new boolean[rows][cols];
for (int r = 0; r < rows; r++) {
dfs(heights, pacific, r, 0);
dfs(heights, atlantic, r, cols - 1);
}
for (int c = 0; c < cols; c++) {
dfs(heights, pacific, 0, c);
dfs(heights, atlantic, rows - 1, c);
}
List<int[]> result = new ArrayList<>();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (pacific[r][c] && atlantic[r][c])
result.add(new int[]{r, c});
return result;
}
private void dfs(int[][] heights, boolean[][] visited, int r, int c) {
visited[r][c] = true;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < heights.length && nc >= 0 && nc < heights[0].length
&& !visited[nr][nc] && heights[nr][nc] >= heights[r][c]) {
dfs(heights, visited, nr, nc);
}
}
}
}
Why reverse the flow direction?
The naive approach tests every cell by running a BFS or DFS to see if water from that cell reaches both oceans. That is extremely expensive because you run a full search from each of the m x n cells.
Reversing the flow means starting from each ocean's border and climbing uphill. A cell reached by this reversed search can drain water downhill back to that ocean. This turns m x n separate searches into just two border-seeded sweeps, each visiting every cell at most once.
// Naive: O((m*n)^2) - search from every cell
// Reversed: O(m*n) - two border-seeded sweeps
// The reversed DFS condition:
// if (heights[nr][nc] >= heights[r][c]) // climb uphill
// This models: water at [nr][nc] can flow DOWN to [r][c]
How does the DFS work internally?
Each DFS starts from a border cell and explores all four neighbors. A neighbor is visited only if its height is greater than or equal to the current cell's height (climbing uphill) and it has not already been marked. Marking a cell means water from that cell can reach the ocean that seeded the search.
// DFS from Pacific border cell (0, 0):
// heights = [[3, 3, 3],
// [3, 1, 3],
// [3, 3, 3]]
// Pacific seeds: top row (0,0),(0,1),(0,2) and left col (1,0),(2,0)
// From (0,0): height=3, neighbors (0,1)=3 >= 3 -> visit
// From (1,0): height=3, neighbor (1,1)=1 < 3 -> skip
// Center cell (1,1) is NOT reachable from Pacific border
How do you use BFS instead of DFS?
BFS is an alternative to DFS for this problem. You seed a queue with all border cells for one ocean, then process the queue level by level, climbing uphill. The result is identical.
package com.bank.service;
import java.util.*;
public class PacificAtlanticBFS {
private static final int[][] DIRS = {{0,1},{0,-1},{1,0},{-1,0}};
public List<int[]> pacificAtlantic(int[][] heights) {
int rows = heights.length, cols = heights[0].length;
boolean[][] pacific = new boolean[rows][cols];
boolean[][] atlantic = new boolean[rows][cols];
Queue<int[]> pQueue = new LinkedList<>();
Queue<int[]> aQueue = new LinkedList<>();
for (int r = 0; r < rows; r++) {
pQueue.offer(new int[]{r, 0}); pacific[r][0] = true;
aQueue.offer(new int[]{r, cols-1}); atlantic[r][cols-1] = true;
}
for (int c = 0; c < cols; c++) {
pQueue.offer(new int[]{0, c}); pacific[0][c] = true;
aQueue.offer(new int[]{rows-1, c}); atlantic[rows-1][c] = true;
}
bfs(heights, pacific, pQueue);
bfs(heights, atlantic, aQueue);
List<int[]> result = new ArrayList<>();
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
if (pacific[r][c] && atlantic[r][c])
result.add(new int[]{r, c});
return result;
}
private void bfs(int[][] heights, boolean[][] visited, Queue<int[]> queue) {
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : DIRS) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < heights.length && nc >= 0 && nc < heights[0].length
&& !visited[nr][nc] && heights[nr][nc] >= heights[cell[0]][cell[1]]) {
visited[nr][nc] = true;
queue.offer(new int[]{nr, nc});
}
}
}
}
}
How is DFS different from BFS here?
| Aspect | DFS | BFS |
|---|---|---|
| Implementation | Recursive or explicit stack | Queue-based |
| Space | O(m*n) for recursion stack in worst case | O(m*n) for queue in worst case |
| Order of exploration | Depth-first, follows one path deep | Level-by-level from border |
| Result | Identical reachability sets | Identical reachability sets |
| Risk | Stack overflow on very large grids | No stack overflow risk |
// DFS: simpler code, risk of stack overflow on large grids
// BFS: slightly more code, safer for production with large grids
What are the edge cases?
A single-cell grid always reaches both oceans because that cell is on all four borders. A grid where all heights are equal means every cell reaches both oceans. A grid that slopes strictly from top-left to bottom-right may have only the top-left corner reaching the Pacific and the bottom-right corner reaching the Atlantic.
package com.bank.service;
public class PacificAtlanticEdgeCases {
public static void main(String[] args) {
PacificAtlanticFlow solver = new PacificAtlanticFlow();
// Single cell: always reaches both
int[][] single = {{5}};
System.out.println(solver.pacificAtlantic(single).size()); // 1
// All equal: every cell reaches both
int[][] flat = {{3,3},{3,3}};
System.out.println(solver.pacificAtlantic(flat).size()); // 4
}
}
1
4
What are common mistakes?
The most common mistake is forgetting to reverse the flow direction, comparing heights[nr][nc] <= heights[r][c] instead of >=. That would search downhill from the border, which marks cells the ocean can flood rather than cells that can drain to the ocean.
// WRONG: searching downhill from border
if (heights[nr][nc] <= heights[r][c]) { ... } // Bug!
// CORRECT: searching uphill from border (reversed flow)
if (heights[nr][nc] >= heights[r][c]) { ... }
Another mistake is not seeding all border cells. The Pacific border includes both the top row and the left column, and the Atlantic border includes both the bottom row and the right column.
What should a senior engineer know?
A senior engineer should understand that the key insight is the reversal of direction. Searching outward from every cell to both oceans is O((m*n)^2), while seeding from the borders and climbing uphill is O(m*n). The equal-or-greater comparison correctly models the reversed downhill flow.
For very large grids, prefer BFS over recursive DFS to avoid stack overflow. The iterative DFS with an explicit stack is equally safe.
What are common interview follow-up questions?
- Interviewers commonly ask:
- Why reverse the flow? (Reduces m*n searches to two border-seeded sweeps.)
- What is the time complexity? (O(m*n) because each cell is visited at most twice.)
- DFS or BFS? (Both work; BFS avoids stack overflow on large grids.)
- What if water flows only to strictly lower neighbors? (Change >= to > in the reversed search.)
Visual Overview
Grid of heights: ┌─────────────┐ │ 1 2 2 3 │ ← Pacific (top) │ 3 2 3 4 │ │ 2 4 5 3 │ │ 6 7 1 4 │ │ 5 1 1 2 │ ← Atlantic (bottom) └─────────────┘ ↑ ↑ Pacific Atlantic (left) (right) Step 1: DFS/BFS from Pacific border (top + left) ┌─────────────┐ │ P P P P │ │ P P P P │ │ P P P . │ │ P P . . │ │ P . . . │ └─────────────┘ Step 2: DFS/BFS from Atlantic border (bottom + right) ┌─────────────┐ │ . . . A │ │ . . A A │ │ . A A A │ │ A A A A │ │ A A A A │ └─────────────┘ Step 3: Intersection (P and A) ┌─────────────┐ │ . . . X │ │ . . X X │ │ . X X . │ │ X X . . │ │ X . . . │ └─────────────┘ X = cells reaching both oceans
Key Takeaway
Pacific Atlantic Water Flow asks which cells in a height grid can drain water to both the Pacific and Atlantic oceans. The naive approach runs a search from every cell to test both-ocean reachability, which is extremely expensive. The efficient solution reverses the flow: start from each ocean's border cells and climb uphill, moving only to neighbors of equal or greater height.
Two boolean matrices, one per ocean, mark every cell each search can reach. A marked cell means water from that cell can flow downhill back to the ocean that seeded the search. After both sweeps, the answer is every cell marked in both matrices.
The reversal of direction is the insight interviewers test. It turns per-cell outward searches into just two linear border-seeded sweeps, bringing the time from O((m*n)^2) down to O(m*n). The equal-or-greater comparison in the reversed DFS correctly models the reversed downhill flow.
In a settlement-terrain model at the National Bank of India, each cell has a height representing a balance level, and liquidity drains downhill to two settlement pools bordered by opposite edges. Finding cells that feed both pools is this exact problem, and seeding the search from each pool's border and climbing uphill computes both reachable sets in two linear passes.
Remember one sentence: reverse the flow by climbing uphill from each ocean's border, mark the two reachability sets, and return their intersection.
---