417. Pacific Atlantic Water Flow

MediumDepth-First SearchBreadth-First SearchArrayMatrix

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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Example 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 and vis2 for the Pacific and Atlantic oceans, respectively.
We also initialize two queues q1 and q2 for the BFS process.

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:

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

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 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.
Repeat step 5 for q2 and vis2.

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:

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

Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]dp[i] = dp[i - 1] + 1dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]dp[i] = dp[i - 1]

I don’t know

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 and vis2 sets, as well as q1 and q2 queues, involve iterating over all the border cells, which in the worst case involves 2m + 2n - 4 operations, since there are m + 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 to bfs function processes every cell at most once, because once a cell is visited, it's added to the corresponding visited set (vis1 or vis2) and will not be processed again. Therefore, each BFS call has a complexity of at most O(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 and vis2, each of which may hold at most m * n elements if all the cells are reachable from both oceans.
Each queue q1 and q2 could in the worst case hold the border cells which are 2(m + n - 2) as discussed earlier, but since this is bounded by O(m + n), it is smaller than the space needed for the vis1 and vis2 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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsetsGenerating random numbersGenerating permutationsSorting integers

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

417. Pacific Atlantic Water Flow

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings