417. Pacific Atlantic Water Flow
Problem Description
The problem presents a scenario where you have a rectangular island bordered by two oceans—the Pacific Ocean on the left and top edges, and the Atlantic Ocean on the right and bottom edges. The island consists of a grid of cells described by an m x n
matrix, where each cell has a certain height above sea level.
Rainwater can flow from higher or equal height cells to adjacent lower or equal height cells. The goal is to figure out from which cells on the island the water can flow to both oceans. This is a standard graph traversal problem where water flow is analogous to visiting nodes (cells) of the graph.
Flowchart Walkthrough
To analyze LeetCode 417. Pacific Atlantic Water Flow using the algorithm flowchart, let’s follow the decision-making steps:
Is it a graph?
- Yes: The matrix can be treated as a graph where each cell is a node, and edges exist between adjacent cells (up, down, left, right).
Is it a tree?
- No: As the graph represents cells in a matrix, it does not have a single root or a hierarchical structure typically seen in a tree.
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem handles flow in a matrix not governed by acyclic properties but rather by the topographical elevation constraints of each cell that determine where water can flow.
Is the problem related to shortest paths?
- No: The problem focuses on identifying cells from which water can flow to both the Pacific and Atlantic oceans, not finding the shortest path.
Does the problem involve connectivity?
- Yes: The task involves determining connectivity from cells to the borders (edges of the matrix) that represent the two oceans.
Is the graph weighted?
- No: The grid does not have weighted edges; it simply follows a rule where water flows from cells of higher or equal height to cells of lower or equal height.
Conclusion: According to the flowchart, after determining the connectivity in an unweighted graph, we realize Depth-First Search (DFS) is the suitable method to explore each cell’s connection to the ocean borders, respecting the problem constraints. Although the flowchart suggests BFS as an alternative, DFS is particularly effective here for managing to check all paths from a given cell to the ocean borders recursively.
Intuition
To solve this problem, one can use a Breadth-first search (BFS) approach from the ocean's perspective—starting from the ocean, go inland and figure out all the cells that can flow into this ocean. This is done by traversing the grid starting from the edges adjacent to the oceans and moving to cells of greater or equal height inland, as the water can only flow from high to low or equal height areas.
We use two search processes— one for each ocean. For the Pacific, we start from the top edge and the left edge of the grid because these are the sides bordering the Pacific Ocean. Similarly, for the Atlantic, we start from the bottom edge and the right edge.
As we perform BFS, we keep track of the cells visited (those that can flow into the current ocean) by using a visited set for each ocean. After completing the searches, the result will be the intersection of these two sets—that is, all the cells that can flow into both the Pacific and Atlantic oceans.
Learn more about Depth-First Search and Breadth-First Search patterns.
Solution Approach
The solution implements a Breadth-first search (BFS) algorithm. Here's a breakdown of its implementation:
-
Two sets
vis1
andvis2
are used to keep track of cells that can flow into the Pacific and Atlantic oceans, respectively. -
Two queues
q1
andq2
are initialized to perform separate BFS for the Pacific and Atlantic oceans. -
The matrix's border cells that border the Pacific (
i == 0 or j == 0
) are added toq1
and marked invis1
. Analogously, the border cells that border the Atlantic (i == m - 1 or j == n - 1
) are added toq2
and marked invis2
. -
The
bfs
function is defined, which will take a queue and a visited set as arguments. This function dequeues a cell from the queue, checks its four adjacent cells (north, south, east, west), and if an adjacent cell is within bounds, not yet visited, and its height is greater than or equal to the current cell's height, it marks this cell as visited and enqueues it. -
The
bfs
function is called for bothq1
andvis1
and then forq2
andvis2
. -
Once both BFS traversals are complete, the result is calculated as the intersection of
vis1
andvis2
. This is done by iterating through the entire grid and adding the cell to the result list if it's present in both visited sets. -
The algorithm uses a deque data structure from Python's
collections
module to perform efficient BFS.
The key algorithmic concept here is that of reverse-flow, starting from the destination (oceans) and moving upstream to discover all source points (cells that can flow into the ocean). By approaching the problem from the ocean's perspective rather than from each cell on the island, we avoid the complexity of checking each cell's individual paths to both oceans.
This solution highlights the application of graph traversal algorithms in a grid-like domain and exploits the fact that BFS efficiently explores all reachable nodes in a level-order fashion, which is essential for this type of water flow problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach let's consider a small 3x3 island matrix as an example:
1Pacific ~ ~ ~
2 ~ 1 2 3 ~ Atlantic
3 ~ 8 9 4 ~
4 ~ 7 6 5 ~
5 ~ ~ ~
The numbers represent the height of each cell. Now let's walk through the Breadth-first search (BFS) algorithm:
-
We initialize two sets
vis1
andvis2
for the Pacific and Atlantic oceans, respectively. -
We also initialize two queues
q1
andq2
for the BFS process. -
Add all cells that border the Pacific Ocean (top and left edges,
i == 0 or j == 0
) toq1
and mark them invis1
. For our matrix, these are the cells(0,0),(0,1),(0,2),(1,0),(2,0)
. The Pacific queue and visited set will look as follows:1q1 = [(0,0), (0,1), (0,2), (1,0), (2,0)] 2vis1 = {(0,0), (0,1), (0,2), (1,0), (2,0)}
-
Similarly, add all cells that border the Atlantic Ocean (bottom and right edges,
i == m - 1 or j == n - 1
) toq2
and mark them invis2
. For our matrix, these are the cells(0,2),(1,2),(2,2),(2,1),(2,0)
. The Atlantic queue and visited set will look as follows:1q2 = [(0,2), (1,2), (2,2), (2,1), (2,0)] 2vis2 = {(0,2), (1,2), (2,2), (2,1), (2,0)}
-
Perform BFS starting from
q1
andvis1
. Dequeue(0,0)
fromq1
and explore its neighbor(1,0)
. Since(1,0)
is already invis1
, continue dequeuing and exploring other cells. We check each dequeued cell's neighbors and if a neighbor's height is greater than or equal to the current cell and it's not already visited, we add it to the queue and to the visited set. -
Repeat step 5 for
q2
andvis2
. -
After performing BFS from both oceans, we find the intersection of
vis1
andvis2
to get cells that can flow into both oceans. This results in:1result = vis1.intersection(vis2) 2 = {(0,2), (1,2), (2,2), (2,1), (2,0)}
Thus, in this example, cells (0,2), (1,2), (2,2), (2,1), and (2,0)
are the ones where water can flow to both the Pacific and Atlantic oceans. Notice that in this particular example, due to the setup and heights, all cells can flow to both oceans. However, in a more complex matrix with varying heights, only a subset of the cells would be in the final result.
Solution Implementation
1from collections import deque
2
3class Solution:
4 def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
5 # Helper function: performs BFS from the initial cells in queue
6 def bfs(queue, visited):
7 while queue:
8 # Iterate through current layer
9 for _ in range(len(queue)):
10 row, col = queue.popleft()
11 for delta_row, delta_col in [(0, -1), (0, 1), (1, 0), (-1, 0)]:
12 new_row, new_col = row + delta_row, col + delta_col
13 # Check if the new cell is within bounds, not visited and height >= current
14 if (0 <= new_row < num_rows \
15 and 0 <= new_col < num_columns \
16 and (new_row, new_col) not in visited \
17 and heights[new_row][new_col] >= heights[row][col]):
18
19 visited.add((new_row, new_col))
20 queue.append((new_row, new_col))
21
22 # Initialize rows and columns count
23 num_rows, num_columns = len(heights), len(heights[0])
24
25 # Sets to keep track of cells visited by pacific and atlantic water
26 visited_pacific, visited_atlantic = set(), set()
27
28 # Queues for BFS starting points
29 pacific_queue = deque()
30 atlantic_queue = deque()
31
32 # Initialize the queues and visited sets with the border cells
33 for row in range(num_rows):
34 for col in range(num_columns):
35 if row == 0 or col == 0: # Pacific ocean border
36 visited_pacific.add((row, col))
37 pacific_queue.append((row, col))
38 if row == num_rows - 1 or col == num_columns - 1: # Atlantic ocean border
39 visited_atlantic.add((row, col))
40 atlantic_queue.append((row, col))
41
42 # Run BFS for both oceans
43 bfs(pacific_queue, visited_pacific)
44 bfs(atlantic_queue, visited_atlantic)
45
46 # Collect cells that can reach both oceans
47 return [(row, col) for row in range(num_rows) for col in range(num_columns)
48 if (row, col) in visited_pacific and (row, col) in visited_atlantic]
49
1import java.util.*;
2
3class Solution {
4 private int[][] heightsMatrix;
5 private int height;
6 private int width;
7
8 public List<List<Integer>> pacificAtlantic(int[][] heights) {
9 // dimensions of the input matrix
10 height = heights.length;
11 width = heights[0].length;
12 this.heightsMatrix = heights;
13
14 // queues for BFS from Pacific and Atlantic oceans
15 Deque<int[]> pacificQueue = new LinkedList<>();
16 Deque<int[]> atlanticQueue = new LinkedList<>();
17
18 // visited sets for Pacific and Atlantic oceans
19 Set<Integer> visitedPacific = new HashSet<>();
20 Set<Integer> visitedAtlantic = new HashSet<>();
21
22 // start from the edges of the matrix for both the oceans
23 for (int i = 0; i < height; ++i) {
24 for (int j = 0; j < width; ++j) {
25 if (i == 0 || j == 0) { // Pacific Ocean's edge
26 visitedPacific.add(i * width + j);
27 pacificQueue.offer(new int[]{i, j});
28 }
29 if (i == height - 1 || j == width - 1) { // Atlantic Ocean's edge
30 visitedAtlantic.add(i * width + j);
31 atlanticQueue.offer(new int[]{i, j});
32 }
33 }
34 }
35
36 // perform a BFS for each ocean to find all cells reachable from each ocean
37 bfs(pacificQueue, visitedPacific);
38 bfs(atlanticQueue, visitedAtlantic);
39
40 // results list for cells that can reach both oceans
41 List<List<Integer>> results = new ArrayList<>();
42 for (int i = 0; i < height; ++i) {
43 for (int j = 0; j < width; ++j) {
44 int cellIndex = i * width + j;
45 // if a cell is reachable from both Pacific and Atlantic, add it to results
46 if (visitedPacific.contains(cellIndex) && visitedAtlantic.contains(cellIndex)) {
47 results.add(Arrays.asList(i, j));
48 }
49 }
50 }
51
52 return results;
53 }
54
55 private void bfs(Deque<int[]> queue, Set<Integer> visited) {
56 int[] directions = {-1, 0, 1, 0, -1}; // representational array for traversing neighbors
57
58 while (!queue.isEmpty()) {
59 // explore all the current level's nodes
60 for (int k = queue.size(); k > 0; --k) {
61 int[] cell = queue.poll();
62 // traverse all 4 directions (up, right, down, left)
63 for (int i = 0; i < 4; ++i) {
64 int newRow = cell[0] + directions[i];
65 int newCol = cell[1] + directions[i + 1];
66 // check for valid coordinates and if the cell is not already visited
67 if (newRow >= 0 && newRow < height && newCol >= 0 && newCol < width
68 && !visited.contains(newRow * width + newCol)
69 && heightsMatrix[newRow][newCol] >= heightsMatrix[cell[0]][cell[1]]) {
70 // if criteria are met, add the cell to visited and queue for further BFS
71 visited.add(newRow * width + newCol);
72 queue.offer(new int[]{newRow, newCol});
73 }
74 }
75 }
76 }
77 }
78}
79
1#include <vector>
2#include <queue>
3#include <unordered_set>
4using namespace std;
5
6class Solution {
7public:
8 vector<vector<int>> matrixHeights;
9 int rows;
10 int cols;
11
12 // This method will be used to find all cells that can reach both the Pacific and Atlantic oceans.
13 vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
14 rows = heights.size();
15 cols = heights[0].size();
16 this->matrixHeights = heights;
17 queue<pair<int, int>> pacificQueue;
18 queue<pair<int, int>> atlanticQueue;
19 unordered_set<int> pacificVisited;
20 unordered_set<int> atlanticVisited;
21
22 // Initialize the queues with cells adjacent to the Pacific and Atlantic oceans.
23 for (int i = 0; i < rows; ++i) {
24 for (int j = 0; j < cols; ++j) {
25 if (i == 0 || j == 0) {
26 pacificVisited.insert(i * cols + j);
27 pacificQueue.emplace(i, j);
28 }
29 if (i == rows - 1 || j == cols - 1) {
30 atlanticVisited.insert(i * cols + j);
31 atlanticQueue.emplace(i, j);
32 }
33 }
34 }
35
36 // Perform BFS for both the Pacific and Atlantic oceans.
37 bfs(pacificQueue, pacificVisited);
38 bfs(atlanticQueue, atlanticVisited);
39
40 // Collect cells that can reach both oceans.
41 vector<vector<int>> answer;
42 for (int i = 0; i < rows; ++i) {
43 for (int j = 0; j < cols; ++j) {
44 int cellIndex = i * cols + j;
45 if (pacificVisited.count(cellIndex) && atlanticVisited.count(cellIndex)) {
46 answer.push_back({i, j});
47 }
48 }
49 }
50 return answer;
51 }
52
53 // This method performs Breadth-First Search (BFS) starting from the cells adjacent to a given ocean.
54 void bfs(queue<pair<int, int>>& q, unordered_set<int>& visited) {
55 vector<int> directions = {-1, 0, 1, 0, -1};
56 while (!q.empty()) {
57 auto cell = q.front();
58 q.pop();
59 for (int i = 0; i < 4; ++i) {
60 int x = cell.first + directions[i];
61 int y = cell.second + directions[i + 1];
62 // Check for the valid cell and that the new cell's height is not less than the current cell's height
63 if (x >= 0 && x < rows && y >= 0 && y < cols && !visited.count(x * cols + y) && matrixHeights[x][y] >= matrixHeights[cell.first][cell.second]) {
64 visited.insert(x * cols + y);
65 q.emplace(x, y);
66 }
67 }
68 }
69 }
70};
71
1// Define the main function that returns all cells that have water flowing to both the Pacific and Atlantic ocean
2function pacificAtlantic(heights: number[][]): number[][] {
3 const rowCount = heights.length; // Number of rows
4 const colCount = heights[0].length; // Number of columns
5 // Directions for moving up, down, left, or right
6 const directions = [
7 [1, 0], // move down
8 [0, 1], // move right
9 [-1, 0], // move up
10 [0, -1], // move left
11 ];
12 // Grid to track the number of oceans each cell can flow to
13 const grid = new Array(rowCount).fill(0).map(() => new Array(colCount).fill(0));
14 // Visited matrix to prevent revisiting cells
15 const visited = new Array(rowCount).fill(0).map(() => new Array(colCount).fill(false));
16
17 // Define the depth-first search function to explore the grid
18 const dfs = (row: number, col: number) => {
19 if (visited[row][col]) {
20 return;
21 }
22 grid[row][col]++;
23 visited[row][col] = true;
24 const height = heights[row][col];
25 // Explore adjacent cells
26 for (const [dx, dy] of directions) {
27 const newRow = row + dx;
28 const newCol = col + dy;
29 // Check if the adjacent cell is within bounds and its height is higher or equal
30 if (height <= (heights[newRow]?.[newCol] ?? -1)) {
31 dfs(newRow, newCol);
32 }
33 }
34 };
35
36 // Flow from the Pacific Ocean (top and left edges)
37 for (let col = 0; col < colCount; col++) {
38 dfs(0, col);
39 }
40 for (let row = 0; row < rowCount; row++) {
41 dfs(row, 0);
42 }
43 // Reset visited cells before starting from the Atlantic Ocean (bottom and right edges)
44 visited.forEach(row => row.fill(false));
45
46 // Flow from the Atlantic Ocean (bottom and right edges)
47 for (let col = 0; col < colCount; col++) {
48 dfs(rowCount - 1, col);
49 }
50 for (let row = 0; row < rowCount; row++) {
51 dfs(row, colCount - 1);
52 }
53
54 // Collect cells where the water can flow to both oceans
55 const results: number[][] = [];
56 for (let row = 0; row < rowCount; row++) {
57 for (let col = 0; col < colCount; col++) {
58 if (grid[row][col] === 2) { // If water flows to both oceans
59 results.push([row, col]);
60 }
61 }
62 }
63 return results; // Return the list of cells with dual ocean water flow
64}
65
66// Example of how to use the function:
67// const heights = [[...], [...], ...];
68// const oceanCells = pacificAtlantic(heights);
69// console.log(oceanCells);
70
Time and Space Complexity
Time Complexity
The time complexity of the provided code is O(m * n)
, where m
is the number of rows and n
is the number of columns in the heights
matrix. Here's the breakdown:
-
The initialization and filling of
vis1
andvis2
sets, as well asq1
andq2
queues, involve iterating over all the border cells, which in the worst case involves2m + 2n - 4
operations, since there arem + n - 2
cells on each border. However, this number is still bounded by the size of the matrix and therefore is considered constant relative to the total number of operations. -
The main computational work happens in the two
bfs
calls. Each call tobfs
function processes every cell at most once, because once a cell is visited, it's added to the corresponding visited set (vis1
orvis2
) and will not be processed again. Therefore, each BFS call has a complexity of at mostO(m * n)
. -
The final list comprehension combines the cells visited by both BFS calls, which, in the worst case, checks each cell in the matrix once. So, this is again
O(m * n)
.
Since all these steps are sequential, the overall time complexity remains O(m * n)
.
Space Complexity
The space complexity of the code is also O(m * n)
:
-
We store the visited states for both the Pacific and Atlantic oceans in
vis1
andvis2
, each of which may hold at mostm * n
elements if all the cells are reachable from both oceans. -
Each queue
q1
andq2
could in the worst case hold the border cells which are2(m + n - 2)
as discussed earlier, but since this is bounded byO(m + n)
, it is smaller than the space needed for thevis1
andvis2
sets. -
Temporarily, for BFS, we may also have a queue that stores neighbors to visit. In the worst case, this can contain a number of elements equal to the entire grid (if the higher elevation cells traverse the entire grid), adding to
O(m * n)
. -
The output list in the last list comprehension can hold at most
m * n
coordinates as well, however, the space for the result does not contribute to the space complexity as it is required for the output, not the computation process.
Taking all the above considerations into account, the space needed for the BFS visits and the storing of visited cells results in the total space complexity of O(m * n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.