0417 - Pacific Atlantic Water Flow (Medium)
Problem Statement
There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinatesresultwhereresult[i] = [ri, ci]denotes that rain water can flow from cell(ri, ci)to both the Pacific and Atlantic oceans.
Example 1:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean
[0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean
[1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean
[1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean
[2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean
[3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean
[3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean
[4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.
Example 2:
Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.
Constraints:
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5
Approach 1: DFS
- C++
- Python
class Solution {
public:
void dfs(vector<vector<int>>& M, vector<vector<int>>& vis, int i, int j) {
int m = M.size(), n = M[0].size();
// marked this cell (i, j) as visited
// so that we won't visit it again
vis[i][j] = 1;
// perform DFS on the left cell
if (i - 1 >= 0 && !vis[i - 1][j] && M[i - 1][j] >= M[i][j]) dfs(M, vis, i - 1, j);
// perform DFS on the right cell
if (i + 1 < m && !vis[i + 1][j] && M[i + 1][j] >= M[i][j]) dfs(M, vis, i + 1, j);
// perform DFS on the top cell
if (j - 1 >= 0 && !vis[i][j - 1] && M[i][j - 1] >= M[i][j]) dfs(M, vis, i, j - 1);
// perform DFS on the bottom cell
if (j + 1 < n && !vis[i][j + 1] && M[i][j + 1] >= M[i][j]) dfs(M, vis, i, j + 1);
}
vector<vector<int>> pacificAtlantic(vector<vector<int>>& M) {
vector<vector<int>> ans;
int m = M.size(), n = M[0].size();
// P[i][j] = 1 means it is able to flow to pacific ocean
vector<vector<int>> P(m, vector<int>(n));
// A[i][j] = 1 means it is able to flow to atlantic ocean
vector<vector<int>> A(m, vector<int>(n));
for(int i = 0; i < m; i++) {
// perform dfs starting from the left-most column
dfs(M, P, i, 0);
// perform dfs starting from the right-most column
dfs(M, A, i, n - 1);
}
for(int i = 0; i < n; i++) {
// perform dfs starting from the top-most row
dfs(M, P, 0, i);
// perform dfs starting from the bottom-most row
dfs(M, A, m - 1, i);
}
// iterate each row
for(int i = 0; i < m; i++) {
// iterate each column
for(int j = 0; j < n; j++) {
// if both P[i][j] & A[i][j] are visited
// that means this cell can flow to both ocean
if(P[i][j] && A[i][j]) {
// then put the coordinate (i, j) to answer
ans.push_back(vector<int>{i, j});
}
}
}
return ans;
}
};
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
rows, cols = len(heights), len(heights[0])
# 2 hashsets to maintain all the positions that can reach two oceans
pac, atl = set(), set()
def dfs(r, c, visit, prev_height):
# if position is already been visited or
# if it's out of bounds or if height is to small
if ((r, c) in visit or
r < 0 or c < 0 or r == rows or c == cols or
heights[r][c] < prev_height):
return
# visit new cell
visit.add((r, c))
# run dfs on all four of those neighbours
dfs(r + 1, c, visit, heights[r][c])
dfs(r - 1, c, visit, heights[r][c])
dfs(r, c + 1, visit, heights[r][c])
dfs(r, c - 1, visit, heights[r][c])
# go through every single column in the first row
# for the first row and the last row
for c in range(cols):
dfs(0, c, pac, heights[0][c])
dfs(rows - 1, c, atl, heights[rows - 1][c])
# for the first column and the last column
for r in range(rows):
dfs(r, 0, pac, heights[r][0])
dfs(r, cols - 1, atl, heights[r][cols - 1])
res = []
for r in range(rows):
for c in range(cols):
if (r, c) in pac and (r, c) in atl:
res.append([r, c])
return res
Approach 2: Breadth-First Search
We will start at the "beaches" of each ocean, and find the highest point they reach using BFS. By storing those values in a set and doing it for both oceans, we can return the intersecting points of each set as we know if it rained, those high points will run off into both oceans.
Note: Since we are finding the highest point we can reach from the beaches, we need to check that the cell we are looking at is either taller, or even in height than the cell we came from. If it is shorter, we would avoid continuing.
Time Complexity: where m is the number of rows, and n is the number of columns. Our BFS will traverse each cell, check where they can reach, and will use a set to avoid repeated work.
Space Complexity: . We will maintain 2 hash sets of points we can reach, as well as our queue will take up to space.
- Python
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
# initialize the number of rows, cols and our visited sets.
ROWS, COLS = len(heights), len(heights[0])
pacific = set()
atlantic = set()
# BFS algorithm, takes an initial row, column starting point
# as well as a reference to which visited set we are using.
def bfs(r, c, visited):
# initialize q with starting row, col and the height
# of the current cell.
q = deque([(r,c, heights[r][c])])
while q:
# get row, col of current cell, and height of prev cell.
row, col, height = q.popleft()
# check we are in bounds, that we haven't visited the
# cell before and that if the current cells height
# is shorter than the previous cells height.
if (row < 0 or row >= ROWS
or col < 0 or col >= COLS
or (row,col) in visited
or heights[row][col] < height):
continue
# passed our check above we can add cell to visited
visited.add((row,col))
# check 4 adjacent cells to add to the queue.
for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
q.append((row + dr, col + dc, heights[row][col]))
# Our 2 loops here start our algorithm only from the "beach squares.
# Every column in the first/last rows
for col in range(COLS):
# BFS for each column at the pacific and atlantic "beach".
# Pass a reference of the set we are starting our bfs from
# to our algorithm.
bfs(0, col, pacific)
bfs(ROWS - 1, col, atlantic)
# Every row in the first and last columns.
for row in range(ROWS):
# BFS for each row at the pacific and atlantic "beach."
bfs(row, 0, pacific)
bfs(row, COLS - 1, atlantic)
# Return the intersection of points inside our row.
# If they both reached the same high point, we know rain would
# run off into either ocean.
return pacific.intersection(atlantic)