Approach Summary
Reverse DFS from ocean borders inward. Cells reachable from both oceans are the answer.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Reverse Flow DFS from Ocean Borders (Optimal) | O(M * N) | O(M * N) | Traces flow uphill from the border cells of each ocean inward; intersection of reachable cells yields the solution. |
| 2 Approach 2: Multi-Source BFS from Oceans | O(M * N) | O(M * N) | Uses two queues to propagate non-decreasing elevation levels simultaneously from all boundary cells. |
Step 1: Baseline
Approach 1: Reverse Flow DFS from Ocean Borders (Optimal)
Time: O(M * N)
Space: O(M * N)
1. Initialize two 2D visited matrices: `pacific` and `atlantic` of size M x N. 2. Pacific touches row 0 and col 0; Atlantic touches row M-1 and col N-1. 3. Launch DFS from every Pacific border cell (0, j) and (i, 0). DFS only traverses to neighboring cells with equal or greater height. 4. Launch DFS from every Atlantic border cell (M-1, j) and (i, N-1) with the same non-decreasing height rule. 5. Scan all cells (i, j); if both `pacific[i][j]` and `atlantic[i][j]` are marked true, add `[i, j]` to the result list.
Approach 1: Reverse Flow DFS from Ocean Borders (Optimal) Implementation
Approach 1: Reverse Flow DFS from Ocean Borders (Optimal)
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(heights, i, 0, Integer.MIN_VALUE, pac);
dfs(heights, i, n - 1, Integer.MIN_VALUE, atl);
}
for (int j = 0; j < n; j++) {
dfs(heights, 0, j, Integer.MIN_VALUE, pac);
dfs(heights, m - 1, j, Integer.MIN_VALUE, atl);
}
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pac[i][j] && atl[i][j]) res.add(Arrays.asList(i, j));
}
}
return res;
}
void dfs(int[][] h, int r, int c, int prev, boolean[][] ocean) {
if (r < 0 || c < 0 || r >= h.length || c >= h[0].length || ocean[r][c] || h[r][c] < prev) return;
ocean[r][c] = true;
dfs(h, r + 1, c, h[r][c], ocean);
dfs(h, r - 1, c, h[r][c], ocean);
dfs(h, r, c + 1, h[r][c], ocean);
dfs(h, r, c - 1, h[r][c], ocean);
}
}class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<vector<bool>> pac(m, vector<bool>(n, false)), atl(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
dfs(heights, i, 0, INT_MIN, pac);
dfs(heights, i, n - 1, INT_MIN, atl);
}
for (int j = 0; j < n; j++) {
dfs(heights, 0, j, INT_MIN, pac);
dfs(heights, m - 1, j, INT_MIN, atl);
}
vector<vector<int>> res;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pac[i][j] && atl[i][j]) res.push_back({i, j});
}
}
return res;
}
void dfs(vector<vector<int>>& h, int r, int c, int prev, vector<vector<bool>>& ocean) {
if (r < 0 || c < 0 || r >= h.size() || c >= h[0].size() || ocean[r][c] || h[r][c] < prev) return;
ocean[r][c] = true;
dfs(h, r + 1, c, h[r][c], ocean);
dfs(h, r - 1, c, h[r][c], ocean);
dfs(h, r, c + 1, h[r][c], ocean);
dfs(h, r, c - 1, h[r][c], ocean);
}
};class Solution:
def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
m, n = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, visit, prev):
if (r, c) in visit or r < 0 or c < 0 or r >= m or c >= n or heights[r][c] < prev:
return
visit.add((r, c))
for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
dfs(r + dr, c + dc, visit, heights[r][c])
for c in range(n):
dfs(0, c, pac, heights[0][c])
dfs(m - 1, c, atl, heights[m - 1][c])
for r in range(m):
dfs(r, 0, pac, heights[r][0])
dfs(r, n - 1, atl, heights[r][n - 1])
return [list(cell) for cell in pac & atl]var pacificAtlantic = function(heights) {
const m = heights.length, n = heights[0].length;
const pac = Array.from({length: m}, () => new Array(n).fill(false));
const atl = Array.from({length: m}, () => new Array(n).fill(false));
function dfs(r, c, ocean, prev) {
if (r < 0 || c < 0 || r >= m || c >= n || ocean[r][c] || heights[r][c] < prev) return;
ocean[r][c] = true;
dfs(r + 1, c, ocean, heights[r][c]);
dfs(r - 1, c, ocean, heights[r][c]);
dfs(r, c + 1, ocean, heights[r][c]);
dfs(r, c - 1, ocean, heights[r][c]);
}
for (let i = 0; i < m; i++) {
dfs(i, 0, pac, -1);
dfs(i, n - 1, atl, -1);
}
for (let j = 0; j < n; j++) {
dfs(0, j, pac, -1);
dfs(m - 1, j, atl, -1);
}
const res = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (pac[i][j] && atl[i][j]) res.push([i, j]);
}
}
return res;
}; Step 2: Most Optimized
Approach 2: Multi-Source BFS from Oceans
Time: O(M * N)
Space: O(M * N)
1. Initialize two queues `pacQueue` and `atlQueue` with all respective coastal border cells. 2. Perform standard BFS for each queue: pop cell `(r, c)`, check 4 neighbors, and enqueue neighbors that have `heights[nr][nc] >= heights[r][c]` and haven't been visited yet. 3. Return all coordinates visited by both Pacific and Atlantic BFS queues.
Approach 2: Multi-Source BFS from Oceans Implementation
Approach 2: Multi-Source BFS from Oceans
class Solution {
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
Queue<int[]> pacQ = new ArrayDeque<>(), atlQ = new ArrayDeque<>();
boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
for (int i = 0; i < m; i++) {
pacQ.add(new int[]{i, 0}); pac[i][0] = true;
atlQ.add(new int[]{i, n - 1}); atl[i][n - 1] = true;
}
for (int j = 0; j < n; j++) {
if (!pac[0][j]) { pacQ.add(new int[]{0, j}); pac[0][j] = true; }
if (!atl[m - 1][j]) { atlQ.add(new int[]{m - 1, j}); atl[m - 1][j] = true; }
}
bfs(heights, pacQ, pac);
bfs(heights, atlQ, atl);
List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pac[i][j] && atl[i][j]) res.add(Arrays.asList(i, j));
}
}
return res;
}
void bfs(int[][] h, Queue<int[]> q, boolean[][] visited) {
int[][] dirs = {{1,0}, {-1,0}, {0,1}, {0,-1}};
while (!q.isEmpty()) {
int[] curr = q.poll();
for (int[] d : dirs) {
int nr = curr[0] + d[0], nc = curr[1] + d[1];
if (nr >= 0 && nr < h.length && nc >= 0 && nc < h[0].length && !visited[nr][nc] && h[nr][nc] >= h[curr[0]][curr[1]]) {
visited[nr][nc] = true;
q.add(new int[]{nr, nc});
}
}
}
}
}class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
queue<pair<int, int>> pacQ, atlQ;
vector<vector<bool>> pac(m, vector<bool>(n, false)), atl(m, vector<bool>(n, false));
for (int i = 0; i < m; i++) {
pacQ.push({i, 0}); pac[i][0] = true;
atlQ.push({i, n - 1}); atl[i][n - 1] = true;
}
for (int j = 0; j < n; j++) {
if (!pac[0][j]) { pacQ.push({0, j}); pac[0][j] = true; }
if (!atl[m - 1][j]) { atlQ.push({m - 1, j}); atl[m - 1][j] = true; }
}
auto bfs = [&](queue<pair<int, int>>& q, vector<vector<bool>>& vis) {
int dirs[4][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !vis[nr][nc] && heights[nr][nc] >= heights[r][c]) {
vis[nr][nc] = true;
q.push({nr, nc});
}
}
}
};
bfs(pacQ, pac);
bfs(atlQ, atl);
vector<vector<int>> res;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pac[i][j] && atl[i][j]) res.push_back({i, j});
}
}
return res;
}
};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(starts):
visited = set(starts)
q = deque(starts)
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 visited and heights[nr][nc] >= heights[r][c]:
visited.add((nr, nc))
q.append((nr, nc))
return visited
pac_starts = [(i, 0) for i in range(m)] + [(0, j) for j in range(n)]
atl_starts = [(i, n - 1) for i in range(m)] + [(m - 1, j) for j in range(n)]
return [list(c) for c in bfs(pac_starts) & bfs(atl_starts)]var pacificAtlantic = function(heights) {
const m = heights.length, n = heights[0].length;
function getBfs(starts) {
const visited = Array.from({length: m}, () => new Array(n).fill(false));
const q = [];
for (const [r, c] of starts) {
visited[r][c] = true;
q.push([r, c]);
}
const dirs = [[1,0], [-1,0], [0,1], [0,-1]];
while (q.length > 0) {
const [r, c] = q.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;
q.push([nr, nc]);
}
}
}
return visited;
}
const pacStarts = [];
for (let i = 0; i < m; i++) pacStarts.push([i, 0]);
for (let j = 0; j < n; j++) pacStarts.push([0, j]);
const atlStarts = [];
for (let i = 0; i < m; i++) atlStarts.push([i, n - 1]);
for (let j = 0; j < n; j++) atlStarts.push([m - 1, j]);
const pac = getBfs(pacStarts), atl = getBfs(atlStarts);
const res = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (pac[i][j] && atl[i][j]) res.push([i, j]);
}
}
return res;
};Edge Cases to Watch
- Single cell grid [[1]] — borders both oceans, returns [[0, 0]]
- Flat plateau (all cells have identical height) — water flows freely everywhere, all cells return true
- Strict strictly decreasing slope from center — water flows to oceans from borders and center, all cells reachable
- Strict valley with elevated borders — center cells cannot reach borders
Algorithmic Pattern
View Pattern Guide →
Master the Graphs Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Graphs pattern.
How to Recognize This Pattern
- Flow from borders inward (reverse thinking)
- Two visited sets
Complexity Analysis
Time Complexity
O(m × n)
Space Complexity
O(m × n)
Tags
Graph DFS BFS Matrix
Frequently Asked Questions
What is the optimal time and space complexity for Pacific Atlantic Water Flow?
The optimal solution for Pacific Atlantic Water Flow achieves O(m × n) runtime complexity and requires O(m × n) auxiliary space. Time Complexity is O(M * N) where M is the number of rows and N is the number of columns. Each cell is visited at most once during the Pacific traversal and once during the Atlantic traversal. Space Complexity is O(M * N) to store the two reachability matrices and the recursion/queue call stack.
How do I identify that Pacific Atlantic Water Flow requires the Graphs pattern?
In technical interviews, look for key problem signals: Flow from borders inward (reverse thinking); Two visited sets. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Graphs strategy.
What critical edge cases must be handled in Pacific Atlantic Water Flow?
Essential edge cases to verify include: Single cell grid [[1]] — borders both oceans, returns [[0, 0]]; Flat plateau (all cells have identical height) — water flows freely everywhere, all cells return true; Strict strictly decreasing slope from center — water flows to oceans from borders and center, all cells reachable; Strict valley with elevated borders — center cells cannot reach borders. Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Pacific Atlantic Water Flow?
Pacific Atlantic Water Flow is a Medium-difficulty question tagged with medium recurrence. It is actively asked in technical screening and onsite interview loops at Google, Facebook, Amazon.