Language Selection
Choose your preferred programming language
Showing: Python
Pacific Atlantic Water Flow
Problem Statement
You are given an m x n grid heights describing the elevation of an island. The Pacific Ocean touches the island’s top edge and left edge. The Atlantic Ocean touches the bottom edge and right edge.
Rain falling on a cell can flow to any of its four neighbors (up, down, left, right) whose height is less than or equal to the current cell’s height. Water on a cell in the first row or first column can flow straight into the Pacific, and water on a cell in the last row or last column can flow straight into the Atlantic.
Return the coordinates [r, c] of every cell from which water can reach both oceans. The cells may be returned in any order.
Examples
Example 1:
Input: heights = [[1,2,3],
[8,9,4],
[7,6,5]]
Output: [[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
Explanation: (0,0) and (0,1) are on the top edge, so they reach the Pacific,
but every path toward the bottom or right edge goes uphill, so they never
reach the Atlantic. Every other cell can flow down to both coasts, for
example 9 -> 8 reaches the left edge and 9 -> 6 reaches the bottom edge.
Example 2:
Input: heights = [[5,1,5],
[1,4,1],
[5,1,5]]
Output: [[0,2],[1,1],[2,0]]
Explanation: The center (height 4) flows up to (0,1) for the Pacific and down
to (2,1) for the Atlantic. Corners (0,2) and (2,0) touch both oceans directly.
Corner (0,0) only touches the Pacific, and its lower neighbors are walled in by
higher cells, so it cannot reach the Atlantic. The same holds for (2,2) and
the Pacific.
Example 3:
Input: heights = [[7]]
Output: [[0,0]]
Explanation: A single cell touches all four edges, so it reaches both oceans.
Constraints
1 <= m, n <= 2000 <= heights[r][c] <= 10^5
Approach 1: Search Downhill from Every Cell
Algorithm
The direct reading of the problem: for each cell, simulate where its water can go and check whether it touches both oceans.
- For each cell
(r, c), run a BFS that moves to a neighbor only if the neighbor’s height is less than or equal to the current height. - While searching, record whether any visited cell lies on the top or left edge (Pacific) and whether any lies on the bottom or right edge (Atlantic).
- Stop early once both flags are set. If both are set, add
(r, c)to the answer.
Each search uses its own visited grid, so the work is repeated many times. This is fine for small grids and is a useful baseline, but on a 200 x 200 grid it can do up to 40,000 searches of 40,000 cells each.
Implementation
Python:
from collections import deque
from typing import List
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
result = []
for sr in range(m):
for sc in range(n):
seen = [[False] * n for _ in range(m)]
seen[sr][sc] = True
queue = deque([(sr, sc)])
pacific = atlantic = False
while queue and not (pacific and atlantic):
r, c = queue.popleft()
if r == 0 or c == 0:
pacific = True
if r == m - 1 or c == n - 1:
atlantic = True
# water only moves to neighbors that are not higher
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if (0 <= nr < m and 0 <= nc < n and not seen[nr][nc]
and heights[nr][nc] <= heights[r][c]):
seen[nr][nc] = True
queue.append((nr, nc))
if pacific and atlantic:
result.append([sr, sc])
return result
Java:
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
List<List<Integer>> result = new ArrayList<>();
for (int sr = 0; sr < m; sr++) {
for (int sc = 0; sc < n; sc++) {
boolean[][] seen = new boolean[m][n];
ArrayDeque<int[]> queue = new ArrayDeque<>();
seen[sr][sc] = true;
queue.add(new int[]{sr, sc});
boolean pacific = false, atlantic = false;
while (!queue.isEmpty() && !(pacific && atlantic)) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
if (r == 0 || c == 0) pacific = true;
if (r == m - 1 || c == n - 1) atlantic = true;
// water only moves to neighbors that are not higher
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]
&& heights[nr][nc] <= heights[r][c]) {
seen[nr][nc] = true;
queue.add(new int[]{nr, nc});
}
}
}
if (pacific && atlantic) result.add(List.of(sr, sc));
}
}
return result;
}
}
Go:
func pacificAtlantic(heights [][]int) [][]int {
m, n := len(heights), len(heights[0])
dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
result := [][]int{}
for sr := 0; sr < m; sr++ {
for sc := 0; sc < n; sc++ {
seen := make([][]bool, m)
for i := range seen {
seen[i] = make([]bool, n)
}
seen[sr][sc] = true
queue := [][2]int{{sr, sc}}
pacific, atlantic := false, false
for head := 0; head < len(queue) && !(pacific && atlantic); head++ {
r, c := queue[head][0], queue[head][1]
if r == 0 || c == 0 {
pacific = true
}
if r == m-1 || c == n-1 {
atlantic = true
}
// water only moves to neighbors that are not higher
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc] &&
heights[nr][nc] <= heights[r][c] {
seen[nr][nc] = true
queue = append(queue, [2]int{nr, nc})
}
}
}
if pacific && atlantic {
result = append(result, []int{sr, sc})
}
}
}
return result
}
JavaScript:
/**
* @param {number[][]} heights
* @return {number[][]}
*/
var pacificAtlantic = function (heights) {
const m = heights.length, n = heights[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const result = [];
for (let sr = 0; sr < m; sr++) {
for (let sc = 0; sc < n; sc++) {
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
seen[sr][sc] = true;
const queue = [[sr, sc]];
let pacific = false, atlantic = false;
// array + head index works as a queue without O(n) shift()
for (let head = 0; head < queue.length && !(pacific && atlantic); head++) {
const [r, c] = queue[head];
if (r === 0 || c === 0) pacific = true;
if (r === m - 1 || c === n - 1) atlantic = true;
// water only moves to neighbors that are not higher
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]
&& heights[nr][nc] <= heights[r][c]) {
seen[nr][nc] = true;
queue.push([nr, nc]);
}
}
}
if (pacific && atlantic) result.push([sr, sc]);
}
}
return result;
};
C#:
using System.Collections.Generic;
public class Solution {
private static readonly int[][] Dirs = {
new[] { 1, 0 }, new[] { -1, 0 }, new[] { 0, 1 }, new[] { 0, -1 }
};
public IList<IList<int>> PacificAtlantic(int[][] heights) {
int m = heights.Length, n = heights[0].Length;
var result = new List<IList<int>>();
for (int sr = 0; sr < m; sr++) {
for (int sc = 0; sc < n; sc++) {
var seen = new bool[m, n];
var queue = new Queue<(int r, int c)>();
seen[sr, sc] = true;
queue.Enqueue((sr, sc));
bool pacific = false, atlantic = false;
while (queue.Count > 0 && !(pacific && atlantic)) {
var (r, c) = queue.Dequeue();
if (r == 0 || c == 0) pacific = true;
if (r == m - 1 || c == n - 1) atlantic = true;
// water only moves to neighbors that are not higher
foreach (var d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr, nc]
&& heights[nr][nc] <= heights[r][c]) {
seen[nr, nc] = true;
queue.Enqueue((nr, nc));
}
}
}
if (pacific && atlantic) result.Add(new List<int> { sr, sc });
}
}
return result;
}
}
C++:
#include <queue>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> result;
for (int sr = 0; sr < m; sr++) {
for (int sc = 0; sc < n; sc++) {
vector<vector<bool>> seen(m, vector<bool>(n, false));
queue<pair<int, int>> q;
seen[sr][sc] = true;
q.push({sr, sc});
bool pacific = false, atlantic = false;
while (!q.empty() && !(pacific && atlantic)) {
auto [r, c] = q.front();
q.pop();
if (r == 0 || c == 0) pacific = true;
if (r == m - 1 || c == n - 1) atlantic = true;
// water only moves to neighbors that are not higher
for (const auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]
&& heights[nr][nc] <= heights[r][c]) {
seen[nr][nc] = true;
q.push({nr, nc});
}
}
}
if (pacific && atlantic) result.push_back({sr, sc});
}
}
return result;
}
};
Complexity Analysis
- Time: O((m * n)^2). There are m * n starting cells, and each BFS can visit all m * n cells.
- Space: O(m * n) for one visited grid and queue at a time.
Approach 2: Reverse BFS from Each Ocean (Optimal)
Algorithm
Instead of asking “where can this cell’s water go?” for every cell, ask the reverse question once per ocean: “which cells can drain into this ocean?” Water flows from high to equal-or-lower ground, so walking backwards means climbing from the coast to neighbors of equal or greater height.
- Put every Pacific border cell (row 0 and column 0) into a queue and mark it reachable for the Pacific.
- Run a BFS. From cell
(r, c), move to an unvisited neighbor(nr, nc)only ifheights[nr][nc] >= heights[r][c]. Every cell reached this way can send water down the path you just climbed. - Repeat with the Atlantic border cells (last row and last column) into a second visited grid.
- Return every cell marked in both grids.
Each BFS visits each cell at most once, so the whole thing is linear in the grid size. The searches are iterative, so a 200 x 200 grid cannot overflow the call stack the way a recursive DFS might.
Implementation
Python:
from collections import deque
from typing import List
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
def climb(starts):
# reverse flow: from the coast, move to neighbors that are not lower
reach = [[False] * n for _ in range(m)]
for r, c in starts:
reach[r][c] = True
queue = deque(starts)
while queue:
r, c = queue.popleft()
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if (0 <= nr < m and 0 <= nc < n and not reach[nr][nc]
and heights[nr][nc] >= heights[r][c]):
reach[nr][nc] = True
queue.append((nr, nc))
return reach
pacific = climb([(0, c) for c in range(n)] + [(r, 0) for r in range(1, m)])
atlantic = climb([(m - 1, c) for c in range(n)] + [(r, n - 1) for r in range(m - 1)])
return [[r, c] for r in range(m) for c in range(n)
if pacific[r][c] and atlantic[r][c]]
Java:
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
ArrayDeque<int[]> pacQueue = new ArrayDeque<>(), atlQueue = new ArrayDeque<>();
boolean[][] pacific = new boolean[m][n], atlantic = new boolean[m][n];
// seed each ocean with its border cells
for (int r = 0; r < m; r++) {
mark(pacific, pacQueue, r, 0);
mark(atlantic, atlQueue, r, n - 1);
}
for (int c = 0; c < n; c++) {
mark(pacific, pacQueue, 0, c);
mark(atlantic, atlQueue, m - 1, c);
}
climb(heights, pacific, pacQueue);
climb(heights, atlantic, atlQueue);
List<List<Integer>> result = new ArrayList<>();
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (pacific[r][c] && atlantic[r][c]) result.add(List.of(r, c));
return result;
}
private void mark(boolean[][] reach, ArrayDeque<int[]> queue, int r, int c) {
if (!reach[r][c]) { // corners are seeded twice; enqueue once
reach[r][c] = true;
queue.add(new int[]{r, c});
}
}
// reverse flow: from the coast, move to neighbors that are not lower
private void climb(int[][] heights, boolean[][] reach, ArrayDeque<int[]> queue) {
int m = heights.length, n = heights[0].length;
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reach[nr][nc]
&& heights[nr][nc] >= heights[r][c]) {
reach[nr][nc] = true;
queue.add(new int[]{nr, nc});
}
}
}
}
}
Go:
func pacificAtlantic(heights [][]int) [][]int {
m, n := len(heights), len(heights[0])
dirs := [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
// climb runs a reverse-flow BFS from the given border cells
climb := func(starts [][2]int) [][]bool {
reach := make([][]bool, m)
for i := range reach {
reach[i] = make([]bool, n)
}
queue := make([][2]int, 0, m*n)
for _, s := range starts {
if !reach[s[0]][s[1]] {
reach[s[0]][s[1]] = true
queue = append(queue, s)
}
}
for head := 0; head < len(queue); head++ {
r, c := queue[head][0], queue[head][1]
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
// move uphill (or level): water could flow back down this step
if nr >= 0 && nr < m && nc >= 0 && nc < n && !reach[nr][nc] &&
heights[nr][nc] >= heights[r][c] {
reach[nr][nc] = true
queue = append(queue, [2]int{nr, nc})
}
}
}
return reach
}
var pacStarts, atlStarts [][2]int
for r := 0; r < m; r++ {
pacStarts = append(pacStarts, [2]int{r, 0})
atlStarts = append(atlStarts, [2]int{r, n - 1})
}
for c := 0; c < n; c++ {
pacStarts = append(pacStarts, [2]int{0, c})
atlStarts = append(atlStarts, [2]int{m - 1, c})
}
pacific, atlantic := climb(pacStarts), climb(atlStarts)
result := [][]int{}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if pacific[r][c] && atlantic[r][c] {
result = append(result, []int{r, c})
}
}
}
return result
}
JavaScript:
/**
* @param {number[][]} heights
* @return {number[][]}
*/
var pacificAtlantic = function (heights) {
const m = heights.length, n = heights[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
// reverse flow: from the coast, move to neighbors that are not lower
const climb = (starts) => {
const reach = Array.from({ length: m }, () => new Array(n).fill(false));
const queue = [];
for (const [r, c] of starts) {
if (!reach[r][c]) {
reach[r][c] = true;
queue.push([r, c]);
}
}
for (let head = 0; head < queue.length; head++) {
const [r, c] = queue[head];
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reach[nr][nc]
&& heights[nr][nc] >= heights[r][c]) {
reach[nr][nc] = true;
queue.push([nr, nc]);
}
}
}
return reach;
};
const pacStarts = [], atlStarts = [];
for (let r = 0; r < m; r++) {
pacStarts.push([r, 0]);
atlStarts.push([r, n - 1]);
}
for (let c = 0; c < n; c++) {
pacStarts.push([0, c]);
atlStarts.push([m - 1, c]);
}
const pacific = climb(pacStarts), atlantic = climb(atlStarts);
const result = [];
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (pacific[r][c] && atlantic[r][c]) result.push([r, c]);
return result;
};
C#:
using System.Collections.Generic;
public class Solution {
private static readonly int[][] Dirs = {
new[] { 1, 0 }, new[] { -1, 0 }, new[] { 0, 1 }, new[] { 0, -1 }
};
public IList<IList<int>> PacificAtlantic(int[][] heights) {
int m = heights.Length, n = heights[0].Length;
var pacStarts = new List<(int, int)>();
var atlStarts = new List<(int, int)>();
for (int r = 0; r < m; r++) {
pacStarts.Add((r, 0));
atlStarts.Add((r, n - 1));
}
for (int c = 0; c < n; c++) {
pacStarts.Add((0, c));
atlStarts.Add((m - 1, c));
}
bool[,] pacific = Climb(heights, pacStarts);
bool[,] atlantic = Climb(heights, atlStarts);
var result = new List<IList<int>>();
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (pacific[r, c] && atlantic[r, c]) result.Add(new List<int> { r, c });
return result;
}
// reverse flow: from the coast, move to neighbors that are not lower
private static bool[,] Climb(int[][] heights, List<(int, int)> starts) {
int m = heights.Length, n = heights[0].Length;
var reach = new bool[m, n];
var queue = new Queue<(int r, int c)>();
foreach (var (r, c) in starts) {
if (!reach[r, c]) { // corners appear twice; enqueue once
reach[r, c] = true;
queue.Enqueue((r, c));
}
}
while (queue.Count > 0) {
var (r, c) = queue.Dequeue();
foreach (var d in Dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reach[nr, nc]
&& heights[nr][nc] >= heights[r][c]) {
reach[nr, nc] = true;
queue.Enqueue((nr, nc));
}
}
}
return reach;
}
}
C++:
#include <queue>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<pair<int, int>> pacStarts, atlStarts;
for (int r = 0; r < m; r++) {
pacStarts.push_back({r, 0});
atlStarts.push_back({r, n - 1});
}
for (int c = 0; c < n; c++) {
pacStarts.push_back({0, c});
atlStarts.push_back({m - 1, c});
}
vector<vector<bool>> pacific = climb(heights, pacStarts);
vector<vector<bool>> atlantic = climb(heights, atlStarts);
vector<vector<int>> result;
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (pacific[r][c] && atlantic[r][c]) result.push_back({r, c});
return result;
}
private:
// reverse flow: from the coast, move to neighbors that are not lower
vector<vector<bool>> climb(const vector<vector<int>>& heights,
const vector<pair<int, int>>& starts) {
int m = heights.size(), n = heights[0].size();
const int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<bool>> reach(m, vector<bool>(n, false));
queue<pair<int, int>> q;
for (const auto& [r, c] : starts) {
if (!reach[r][c]) { // corners appear twice; enqueue once
reach[r][c] = true;
q.push({r, c});
}
}
while (!q.empty()) {
auto [r, c] = q.front();
q.pop();
for (const auto& d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reach[nr][nc]
&& heights[nr][nc] >= heights[r][c]) {
reach[nr][nc] = true;
q.push({nr, nc});
}
}
}
return reach;
}
};
Complexity Analysis
- Time: O(m * n). Each of the two searches visits every cell at most once and checks four neighbors per cell, and the final scan is also O(m * n).
- Space: O(m * n) for the two reachability grids and the BFS queues.
Key Insights
- Reverse the direction of flow: searching downhill from every cell repeats work. Searching uphill from the coast answers the question for all cells at once.
- Multi-source BFS: an entire border is one starting set. All border cells go into the queue before the search begins.
- Two independent passes, then intersect: a cell qualifies exactly when it is reachable in both reverse searches.
- Equal heights count: water flows to neighbors of the same height, so the uphill test is
>=, not>.
Edge Cases
- Single cell: it touches both oceans, so the answer is
[[0,0]]. - Single row or single column: every cell touches both oceans directly, so every cell is in the answer.
- Flat grid: all heights equal, so water moves everywhere and every cell qualifies.
- Corners: the top-right and bottom-left corners always qualify because they touch both oceans. The answer is never empty.
- Strict ridges and basins: low interior cells surrounded by higher walls reach neither ocean.
Common Mistakes
- Using
>instead of>=in the reverse search: this drops paths across flat ground. - Flipping the comparison: the reverse search climbs (
neighbor >= current). Using<=there simulates forward flow from the coast, which is meaningless. - Mixing up the coasts: the Pacific is the top and left edges, the Atlantic the bottom and right edges.
- One shared visited grid for both oceans: each ocean needs its own grid so you can intersect them.
- Recursive DFS on a large grid: a 200 x 200 grid with a snake-shaped path can recurse 40,000 levels deep and overflow the stack in some languages. An iterative BFS avoids that.
Interview Tips
- Start by stating the brute force (search from every cell) and its O((m * n)^2) cost, then explain why reversing the flow removes the repetition.
- Say clearly which comparison you use and why it is
>=in the reverse direction. - Mention that BFS and DFS both work for the reverse search. BFS with an explicit queue avoids recursion depth limits.
- Relate it to multi-source BFS problems such as rotting oranges or walls-and-gates.
Follow-up Questions
- Three or more oceans: run one reverse search per ocean and intersect all of them. The cost is O(k * m * n) for k oceans.
- Water that reaches at least one ocean: take the union of the two grids instead of the intersection.
- Diagonal flow: add the four diagonal directions. The algorithm is unchanged.
- Streaming height updates: a single cell change can flip reachability for a large region. Recomputing the affected ocean’s search is the simple answer, and incremental approaches are much harder.