875917. Pacific Atlantic Water Flow
Pacific Atlantic Water Flow
Slug: pacific-atlantic-water-flow
Difficulty: Hard
Id: 875917
Topic Tags: Graph, DFS, BFS, Algorithms
Company Tags: None
Summary
The Pacific Atlantic Water Flow problem involves a 2D matrix representing the elevation of land at each point. The task is to find all points where water can flow from both the Pacific Ocean and the Atlantic Ocean, given that water always flows towards lower elevations.
This problem requires a solid understanding of graph traversal techniques, such as DFS (Depth-First Search) and BFS (Breadth-First Search), to identify the connected components in the elevation map.
Detailed Explanation
The approach to solving this problem is to use a combination of DFS and BFS. First, we need to find all points that are connected to the Pacific Ocean. Then, we can use these points as starting points for our BFS traversal to find all points that are connected to the Atlantic Ocean.
Here's a step-by-step breakdown of the solution:
- Initialize an empty set
pacificto store the points connected to the Pacific Ocean. - Iterate through each cell in the elevation map, and for each cell:
- If the current cell is at or below sea level (0), mark it as visited and add it to the
pacificset. - If the current cell has not been visited before, recursively traverse all its neighboring cells using DFS. Mark each visited neighbor as visited and add it to the
pacificset if its elevation is 0 or lower.
- If the current cell is at or below sea level (0), mark it as visited and add it to the
- Initialize an empty set
atlanticto store the points connected to the Atlantic Ocean. - Iterate through each cell in the elevation map, and for each cell:
- If the current cell is at or below sea level (0), mark it as visited and add it to the
atlanticset. - If the current cell has not been visited before, recursively traverse all its neighboring cells using BFS. Mark each visited neighbor as visited and add it to the
atlanticset if its elevation is 0 or lower.
- If the current cell is at or below sea level (0), mark it as visited and add it to the
- Find the intersection of the
pacificandatlanticsets to get the points where water can flow from both oceans.
Time complexity: O(m * n), where m is the number of rows and n is the number of columns in the elevation map. Space complexity: O(m * n) for storing the visited cells during DFS and BFS traversal.
Optimized Solutions
Java
java
import java.util.*;
public class PacificAtlanticWaterFlow {
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
if (matrix.length == 0) return new ArrayList<>();
int m = matrix.length, n = matrix[0].length;
boolean[][] visitedPacific = new boolean[m][n];
boolean[][] visitedAtlantic = new boolean[m][n];
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < m; i++) {
dfs(matrix, visitedPacific, i, 0);
dfs(matrix, visitedAtlantic, i, n - 1);
}
for (int j = 0; j < n; j++) {
dfs(matrix, visitedPacific, 0, j);
dfs(matrix, visitedAtlantic, m - 1, j);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (visitedPacific[i][j] && visitedAtlantic[i][j]) {
result.add(Arrays.asList(i, j));
}
}
}
return result;
}
private void dfs(int[][] matrix, boolean[][] visited, int i, int j) {
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || visited[i][j] || matrix[i][j] == 0) return;
visited[i][j] = true;
for (int[] dir : {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
int ni = i + dir[0], nj = j + dir[1];
if (ni >= 0 && ni < matrix.length && nj >= 0 && nj < matrix[0].length && !visited[ni][nj] && matrix[ni][nj] > matrix[i][j]) {
dfs(matrix, visited, ni, nj);
}
}
}
}
Python
python
def pacificAtlantic(matrix):
m, n = len(matrix), len(matrix[0])
pacific = [[False]*n for _ in range(m)]
atlantic = [[False]*n for _ in range(m)]
def dfs(i, j):
if i < 0 or i >= m or j < 0 or j >= n or matrix[i][j] == 0: return
pacific[i][j] = True
for d in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
ni, nj = i+d[0], j+d[1]
if 0 <= ni < m and 0 <= nj < n and not pacific[ni][nj] and matrix[ni][nj] > matrix[i][j]:
dfs(ni, nj)
for i in range(m):
dfs(i, 0)
dfs(i, n-1)
for j in range(n):
dfs(0, j)
dfs(m-1, j)
result = []
for i in range(m):
for j in range(n):
if pacific[i][j] and atlantic[i][j]:
result.append([i, j])
return result
C++
cpp
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<bool>> visitedPacific(m, vector<bool>(n));
vector<vector<bool>> visitedAtlantic(m, vector<bool>(n));
for (int i = 0; i < m; i++) {
dfs(matrix, visitedPacific, i, 0);
dfs(matrix, visitedAtlantic, i, n - 1);
}
for (int j = 0; j < n; j++) {
dfs(matrix, visitedPacific, 0, j);
dfs(matrix, visitedAtlantic, m - 1, j);
}
vector<vector<int>> result;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (visitedPacific[i][j] && visitedAtlantic[i][j]) {
result.push_back({i, j});
}
}
}
return result;
}
void dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int i, int j) {
if (i < 0 || i >= matrix.size() || j < 0 || j >= matrix[0].size() || visited[i][j] || matrix[i][j] == 0) return;
visited[i][j] = true;
for (auto dir : {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
int ni = i + dir[0], nj = j + dir[1];
if (ni >= 0 && ni < matrix.size() && nj >= 0 && nj < matrix[0].size()
&& !visited[ni][nj] && matrix[ni][nj] > matrix[i][j]) {
dfs(matrix, visited, ni, nj);
}
}
}
Java
java
import java.util.*;
public class PacificAtlantic {
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
boolean[][] visitedPacific = new boolean[m][n];
boolean[][] visitedAtlantic = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(matrix, visitedPacific, i, 0);
dfs(matrix, visitedAtlantic, i, n - 1);
}
for (int j = 0; j < n; j++) {
dfs(matrix, visitedPacific, 0, j);
dfs(matrix, visitedAtlantic, m - 1, j);
}
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (visitedPacific[i][j] && visitedAtlantic[i][j]) {
result.add(Arrays.asList(i, j));
}
}
}
return result;
}
private void dfs(int[][] matrix, boolean[][] visited, int i, int j) {
if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || visited[i][j] || matrix[i][j] == 0) return;
visited[i][j] = true;
for (int[] dir : {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}) {
int ni = i + dir[0], nj = j + dir[1];
if (ni >= 0 && ni < matrix.length && nj >= 0 && nj < matrix[0].length
&& !visited[ni][nj] && matrix[ni][nj] > matrix[i][j]) {
dfs(matrix, visited, ni, nj);
}
}
}
}
This algorithm is a variation of the Depth-First Search (DFS) algorithm. It uses DFS to mark all cells that are reachable from the Pacific Ocean and those that are reachable from the Atlantic Ocean. Then it checks which cells are reachable from both oceans and returns them as the result.
The time complexity of this algorithm is O(m*n), where m is the number of rows in the matrix and n is the number of columns. The space complexity is also O(m*n) for storing the visited cells.
This problem can be solved using Breadth-First Search (BFS) instead of DFS, but it would require more code to implement the BFS algorithm.
Not available