Log inSign up
mediumLeetCodeNot Started

Pacific Atlantic Water Flow

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's top and left edges, and the Atlantic Ocean touches the island's bottom and right edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean directly into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

---

### Examples

Example 1: ``text 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]] Explanation: The following cells can flow to the Pacific and Atlantic oceans: - (0,4): [0,4] -> Pacific (top) and Atlantic (right) - (1,3): [1,3] -> [0,3] -> Pacific; [1,3] -> [1,4] -> Atlantic - (1,4): [1,4] -> Pacific and Atlantic - (2,2): [2,2] -> [1,2] -> Pacific; [2,2] -> [2,3] -> [2,4] -> Atlantic - (3,0): [3,0] -> Pacific and Atlantic - (3,1): [3,1] -> [3,0] -> Pacific; [3,1] -> [4,1] -> Atlantic - (4,0): [4,0] -> Pacific and Atlantic

Example 2: ``text Input: heights = [[1]] Output: [[0,0]] Explanation: The single cell touches both oceans directly.

---

### Constraints - m == heights.length - n == heights[r].length - 1 <= m, n <= 200 - 0 <= heights[r][c] <= 10^5

Constraints:

  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize when reversing the search direction reduces time complexity from quadratic to linear.
  • Implement multi-source border flood-fill across distinct boundaries.
  • Intersect multiple reachability matrices efficiently.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Bi-directional reachability to two different boundaries
  • Elevation or height-constrained grid flow
  • Reversing flow direction from targets to sources

Algorithmic Decision Tree:

  • Instead of flood from each cell -> Multi-source flood inward from borders.
  • Condition for reverse flow: heights[nr][nc] >= heights[r][c].
  • Find cells where pacific[r][c] && atlantic[r][c] are both true.

Connected Patterns:

Surrounded RegionsNumber of Enclaves01 Matrix

1. Individual Downhill Search from Each Cell

Intuition

Test each cell independently. Launch a downhill search: if water reaches the top or left border, pacific = true; if it reaches the bottom or right border, atlantic = true. If both are true, add (r, c) to the result.

Algorithm

  1. Initialize result list.
  2. Loop r from 0 to m - 1 and c from 0 to n - 1:
  3. Run canReachBoth(r, c) using BFS/DFS with downhill condition heights[nr][nc] <= heights[currR][currC].
  4. If canReachBoth returns true:
  5. result.push([r, c]).
  6. Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6 bool canReachBoth(int startR, int startC, const std::vector<std::vector<int>>& heights) {
7 int m = heights.size(), n = heights[0].size();
8 bool reachP = false, reachA = false;
9 std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
10 std::queue<std::pair<int, int>> q;
11
12 q.push({startR, startC});
13 visited[startR][startC] = true;
14 int dr[] = {-1, 1, 0, 0};
15 int dc[] = {0, 0, -1, 1};
16
17 while (!q.empty()) {
18 auto [r, c] = q.front();
19 q.pop();
20
21 if (r == 0 || c == 0) reachP = true;
22 if (r == m - 1 || c == n - 1) reachA = true;
23 if (reachP && reachA) return true;
24
25 for (int k = 0; k < 4; ++k) {
26 int nr = r + dr[k], nc = c + dc[k];
27 if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited[nr][nc] && heights[nr][nc] <= heights[r][c]) {
28 visited[nr][nc] = true;
29 q.push({nr, nc});
30 }
31 }
32 }
33 return reachP && reachA;
34 }
35public:
36 std::vector<std::vector<int>> pacificAtlantic(std::vector<std::vector<int>>& heights) {
37 std::vector<std::vector<int>> res;
38 int m = heights.size(), n = heights[0].size();
39 for (int r = 0; r < m; ++r) {
40 for (int c = 0; c < n; ++c) {
41 if (canReachBoth(r, c, heights)) {
42 res.push_back({r, c});
43 }
44 }
45 }
46 return res;
47 }
48};
49
50int main() {
51 Solution sol;
52 std::vector<std::vector<int>> heights = {
53 {1,2,2,3,5},
54 {3,2,3,4,4},
55 {2,4,5,3,1},
56 {6,7,1,4,5},
57 {5,1,1,2,4}
58 };
59 auto res = sol.pacificAtlantic(heights);
60 std::cout << "Cells reaching both oceans: " << res.size() << " (Expected: 7)\n";
61 return 0;
62}

Time & Space Complexity

  • Time complexity: O((m * n)^2)
  • Space complexity: O(m * n)

2. Multi-Source BFS from Ocean Borders Uphill

Intuition

Instead of searching downhill from inland, start at the perimeter. Enqueue all Pacific border cells into pacificQueue and Atlantic border cells into atlanticQueue. BFS expands only to neighboring cells with heights[nr][nc] >= heights[r][c] (uphill).

Algorithm

  1. Initialize pacificQueue and atlanticQueue.
  2. Initialize boolean matrices pacific[m][n] and atlantic[m][n] to false.
  3. Add top row and left column to pacificQueue; mark pacific = true.
  4. Add bottom row and right column to atlanticQueue; mark atlantic = true.
  5. Run BFS for pacificQueue and BFS for atlanticQueue (neighbor height >= current height).
  6. Collect all coordinates (r, c) where pacific[r][c] && atlantic[r][c] are true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6 void bfs(std::queue<std::pair<int, int>>& q, std::vector<std::vector<bool>>& reachable, const std::vector<std::vector<int>>& heights) {
7 int m = heights.size(), n = heights[0].size();
8 int dr[] = {-1, 1, 0, 0};
9 int dc[] = {0, 0, -1, 1};
10
11 while (!q.empty()) {
12 auto [r, c] = q.front();
13 q.pop();
14
15 for (int k = 0; k < 4; ++k) {
16 int nr = r + dr[k], nc = c + dc[k];
17 if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
18 reachable[nr][nc] = true;
19 q.push({nr, nc});
20 }
21 }
22 }
23 }
24public:
25 std::vector<std::vector<int>> pacificAtlantic(std::vector<std::vector<int>>& heights) {
26 int m = heights.size(), n = heights[0].size();
27 std::vector<std::vector<bool>> pacific(m, std::vector<bool>(n, false));
28 std::vector<std::vector<bool>> atlantic(m, std::vector<bool>(n, false));
29 std::queue<std::pair<int, int>> pQ, aQ;
30
31 for (int r = 0; r < m; ++r) {
32 pacific[r][0] = true; pQ.push({r, 0});
33 atlantic[r][n - 1] = true; aQ.push({r, n - 1});
34 }
35 for (int c = 0; c < n; ++c) {
36 pacific[0][c] = true; pQ.push({0, c});
37 atlantic[m - 1][c] = true; aQ.push({m - 1, c});
38 }
39
40 bfs(pQ, pacific, heights);
41 bfs(aQ, atlantic, heights);
42
43 std::vector<std::vector<int>> res;
44 for (int r = 0; r < m; ++r) {
45 for (int c = 0; c < n; ++c) {
46 if (pacific[r][c] && atlantic[r][c]) {
47 res.push_back({r, c});
48 }
49 }
50 }
51 return res;
52 }
53};
54
55int main() {
56 Solution sol;
57 std::vector<std::vector<int>> heights = {
58 {1,2,2,3,5},
59 {3,2,3,4,4},
60 {2,4,5,3,1},
61 {6,7,1,4,5},
62 {5,1,1,2,4}
63 };
64 std::cout << "BFS Pacific Atlantic: " << sol.pacificAtlantic(heights).size() << " (Expected: 7)\n";
65 return 0;
66}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. Canonical Multi-Source Reverse DFS from Ocean Borders (Optimal)

Intuition

The cleanest, fastest, and most standard interview approach. Starting from all perimeter cells, depth-first search floods uphill (heights[nr][nc] >= heights[r][c]). Each cell is visited at most once per ocean in strictly linear O(m * n) time.

Algorithm

  1. Initialize boolean matrices pacific[m][n] and atlantic[m][n] to false.
  2. Define dfs(r, c, reachable):
  3. reachable[r][c] = true.
  4. For 4 directions (nr, nc):
  5. If in bounds, !reachable[nr][nc], and heights[nr][nc] >= heights[r][c]:
  6. dfs(nr, nc, reachable).
  7. Run dfs for all cells in top row and left column into pacific matrix.
  8. Run dfs for all cells in bottom row and right column into atlantic matrix.
  9. Collect all coordinates (r, c) where pacific[r][c] && atlantic[r][c] are true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 void dfs(int r, int c, std::vector<std::vector<bool>>& reachable, const std::vector<std::vector<int>>& heights) {
6 reachable[r][c] = true;
7 int m = heights.size(), n = heights[0].size();
8 int dr[] = {-1, 1, 0, 0};
9 int dc[] = {0, 0, -1, 1};
10
11 for (int k = 0; k < 4; ++k) {
12 int nr = r + dr[k], nc = c + dc[k];
13 if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
14 dfs(nr, nc, reachable, heights);
15 }
16 }
17 }
18public:
19 std::vector<std::vector<int>> pacificAtlantic(std::vector<std::vector<int>>& heights) {
20 int m = heights.size(), n = heights[0].size();
21 std::vector<std::vector<bool>> pacific(m, std::vector<bool>(n, false));
22 std::vector<std::vector<bool>> atlantic(m, std::vector<bool>(n, false));
23
24 for (int r = 0; r < m; ++r) {
25 dfs(r, 0, pacific, heights);
26 dfs(r, n - 1, atlantic, heights);
27 }
28 for (int c = 0; c < n; ++c) {
29 dfs(0, c, pacific, heights);
30 dfs(m - 1, c, atlantic, heights);
31 }
32
33 std::vector<std::vector<int>> res;
34 for (int r = 0; r < m; ++r) {
35 for (int c = 0; c < n; ++c) {
36 if (pacific[r][c] && atlantic[r][c]) {
37 res.push_back({r, c});
38 }
39 }
40 }
41 return res;
42 }
43};
44
45int main() {
46 Solution sol;
47 std::vector<std::vector<int>> heights = {
48 {1,2,2,3,5},
49 {3,2,3,4,4},
50 {2,4,5,3,1},
51 {6,7,1,4,5},
52 {5,1,1,2,4}
53 };
54 std::cout << "Canonical DFS Pacific Atlantic: " << sol.pacificAtlantic(heights).size() << " (Expected: 7)\n";
55 return 0;
56}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Downhill Search from Each CellO((m * n)^2)O(m * n)Tests each cell independently downhill until boundaries are reached.Repeated full-grid traversals
2.Multi-Source BFS from Ocean BordersO(m * n)O(m * n)Enqueues all border cells and flows uphill via queue level expansion.Queue memory footprint
3.Canonical Reverse DFS from Ocean BordersOptimalO(m * n)O(m * n)Direct recursive traversal uphill from ocean perimeter with matrix intersection.Call stack depth

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using heights[nr][nc] <= heights[r][c] during reverse traversal, which simulates water flowing downhill from the ocean.

Pitfall 2:

Running independent searches from all cells, causing Time Limit Exceeded (TLE).

Pitfall 3:

Forgetting that water can flow between cells of EQUAL height (>= instead of >).

Crucial Edge Cases to Validate:

  • 1x1 grid (m = 1, n = 1) — Single cell borders both oceans simultaneously, returns [[0, 0]].
  • Flat plateau (all heights identical) — Water flows freely across all cells in all directions; all m*n coordinates are returned.
  • Valley in the center (surrounded by high mountains) — Valley cannot flow downhill to oceans; reverse traversal uphill never enters valley from borders.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State the core insight immediately: 'Reverse the perspective: flow water uphill from ocean borders to achieve O(m*n) time.'
  2. Clearly explain why equal heights (>=) are permitted by the problem statement.
  3. Mention how the intersection of pacific[r][c] && atlantic[r][c] directly yields the result.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does reversing the water flow direction (moving UPHILL from ocean borders) reduce the time complexity from O((m*n)^2) to O(m*n)?

2.Which ocean borders which sides of the island grid?

3.What is the condition for water to flow from (nr, nc) to (r, c) when traversing in REVERSE (uphill)?

Back to DSA Sheet