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:
Pacific ~ ~ ~
~ 1 2 3 ~ Atlantic
~ 8 9 4 ~
~ 7 6 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:q1 = [(0,0), (0,1), (0,2), (1,0), (2,0)] vis1 = {(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:q2 = [(0,2), (1,2), (2,2), (2,1), (2,0)] vis2 = {(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:result = vis1.intersection(vis2) = {(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));