Facebook Pixel

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 and vis2 are used to keep track of cells that can flow into the Pacific and Atlantic oceans, respectively.

  • Two queues q1 and q2 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 to q1 and marked in vis1. Analogously, the border cells that border the Atlantic (i == m - 1 or j == n - 1) are added to q2 and marked in vis2.

  • 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 both q1 and vis1 and then for q2 and vis2.

  • Once both BFS traversals are complete, the result is calculated as the intersection of vis1 and vis2. 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 Evaluator

Example 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:

  1. We initialize two sets vis1 and vis2 for the Pacific and Atlantic oceans, respectively.

  2. We also initialize two queues q1 and q2 for the BFS process.

  3. Add all cells that border the Pacific Ocean (top and left edges, i == 0 or j == 0) to q1 and mark them in vis1. 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)}
  4. Similarly, add all cells that border the Atlantic Ocean (bottom and right edges, i == m - 1 or j == n - 1) to q2 and mark them in vis2. 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)}
  5. Perform BFS starting from q1 and vis1. Dequeue (0,0) from q1 and explore its neighbor (1,0). Since (1,0) is already in vis1, 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.

  6. Repeat step 5 for q2 and vis2.

  7. After performing BFS from both oceans, we find the intersection of vis1 and vis2 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));