Pacific Atlantic Water Flow
Pacific Atlantic Water Flow – Medium Level Problem
You are given a rectangular grid heights where each cell heights[r][c] represents the height of the land at row r and column c.
The grid borders the Pacific Ocean on the top and left edges and the Atlantic Ocean on the bottom and right edges. Water can flow from one cell to another if the neighboring cell has a height that is equal to or lower. Water can also flow directly into the oceans from cells along the grid edges.
Find all cells where water can flow to both the Pacific and Atlantic oceans. Return these cells as a list of [r, c] pairs, representing their row and column.
Example 1:
Input: heights = [
[4,2,7,3,4],
[7,4,6,4,7],
[6,3,5,3,6]
]
Output: [[0,2],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4],[2,0]]
[4,2,7,3,4],
[7,4,6,4,7],
[6,3,5,3,6]
]
Output: [[0,2],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4],[2,0]]
Example 2 :
Input: heights = [[1],[1]]
Output: [[0,0],[0,1]]
Output: [[0,0],[0,1]]
Constraints :
- 1 <= heights.length, heights[r].length <= 100
- 0 <= heights[r][c] <= 1000
Pacific Atlantic Water Flow Problem - Solution
Recommendation for Time and Space Complexity – Aim for a solution with O(m * n) time and space, where m is the number of rows and n is the number of columns.
Hints for solving problems
Hint 1
A brute force method involves checking each cell with BFS to see if it reaches both oceans. However, this results in O((m * n)^2) complexity. Instead, consider a reverse approach.
Hint 2
Use DFS from the grid’s borders: top and left for Pacific, bottom and right for Atlantic. Track reachable cells in two sets, pacific and atlantic. The result is the intersection of these sets.
Hint 3
Run DFS from border cells, adding valid cells to their respective sets. After completing the DFS, check each cell in the grid. If it is in both sets, add it to the result.
There are mainly 2 approach to solve this problem-
- Brute Force(Backtracking) Method
- Depth First Search Method
1. Brute Force(Backtracking) Method
For each cell, use backtracking (DFS or BFS) to check if it can reach both the Pacific and Atlantic oceans. This method is simple but inefficient with a time complexity of O((m * n)^2).
- Time complexity: O(m * n * 4^(m*n))
- Space complexity: O(m * n)
where m is the number of rows and n is the number of columns.
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int ROWS, COLS;
bool pacific, atlantic;
vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
ROWS = heights.size();
COLS = heights[0].size();
vector<vector<int>> res;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
pacific = false;
atlantic = false;
dfs(heights, r, c, INT_MAX);
if (pacific && atlantic) {
res.push_back({r, c});
}
}
}
return res;
}
void dfs(vector<vector<int>>& heights, int r, int c, int prevVal) {
if (r < 0 || c < 0) { pacific = true; return; } if (r >= ROWS || c >= COLS) {
atlantic = true;
return;
}
if (heights[r][c] > prevVal) {
return;
}
int tmp = heights[r][c];
heights[r][c] = INT_MAX;
for (auto& dir : directions) {
dfs(heights, r + dir[0], c + dir[1], tmp);
if (pacific && atlantic) {
break;
}
}
heights[r][c] = tmp;
}
};
Java
public class Solution {
int ROWS, COLS;
boolean pacific, atlantic;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<List> pacificAtlantic(int[][] heights) {
ROWS = heights.length;
COLS = heights[0].length;
List<List> res = new ArrayList<>();
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
pacific = false;
atlantic = false;
dfs(heights, r, c, Integer.MAX_VALUE);
if (pacific && atlantic) {
res.add(Arrays.asList(r, c));
}
}
}
return res;
}
private void dfs(int[][] heights, int r, int c, int prevVal) {
if (r < 0 || c < 0) { pacific = true; return; } if (r >= ROWS || c >= COLS) {
atlantic = true;
return;
}
if (heights[r][c] > prevVal) {
return;
}
int tmp = heights[r][c];
heights[r][c] = Integer.MAX_VALUE;
for (int[] dir : directions) {
dfs(heights, r + dir[0], c + dir[1], tmp);
if (pacific && atlantic) {
break;
}
}
heights[r][c] = tmp;
}
}
Python
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
ROWS, COLS = len(heights), len(heights[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
pacific = atlantic = False
def dfs(r, c, prevVal):
nonlocal pacific, atlantic
if r < 0 or c < 0: pacific = True return if r >= ROWS or c >= COLS:
atlantic = True
return
if heights[r][c] > prevVal:
return
tmp = heights[r][c]
heights[r][c] = float('inf')
for dx, dy in directions:
dfs(r + dx, c + dy, tmp)
if pacific and atlantic:
break
heights[r][c] = tmp
res = []
for r in range(ROWS):
for c in range(COLS):
pacific = False
atlantic = False
dfs(r, c, float('inf'))
if pacific and atlantic:
res.append([r, c])
return res
JavaScript
class Solution {
/**
* @param {number[][]} heights
* @return {number[][]}
*/
pacificAtlantic(heights) {
let ROWS = heights.length, COLS = heights[0].length;
let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let pacific = false, atlantic = false;
const dfs = (r, c, prevVal) => {
if (r < 0 || c < 0) { pacific = true; return; } if (r >= ROWS || c >= COLS) {
atlantic = true;
return;
}
if (heights[r][c] > prevVal) {
return;
}
let tmp = heights[r][c];
heights[r][c] = Infinity;
for (let [dx, dy] of directions) {
dfs(r + dx, c + dy, tmp);
if (pacific && atlantic) {
break;
}
}
heights[r][c] = tmp;
};
let res = [];
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
pacific = false;
atlantic = false;
dfs(r, c, Infinity);
if (pacific && atlantic) {
res.push([r, c]);
}
}
}
return res;
}
}
2. Depth First Search Method
Start DFS from the Pacific and Atlantic borders, marking cells that can flow to each ocean. The result is the intersection of cells reachable from both oceans. This approach is efficient with a time complexity of O(m * n).
- Time complexity: O(m * n)
- Space complexity: O(m * n)
where m is the number of rows and n is the number of columns.
Code
C++
Java
Python
JavaScript
C++
class Solution {
vector<pair<int, int>> directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int ROWS = heights.size(), COLS = heights[0].size();
vector<vector<bool>> pac(ROWS, vector<bool>(COLS, false));
vector<vector<bool>> atl(ROWS, vector<bool>(COLS, false));
for (int c = 0; c < COLS; ++c) {
dfs(0, c, pac, heights);
dfs(ROWS - 1, c, atl, heights);
}
for (int r = 0; r < ROWS; ++r) {
dfs(r, 0, pac, heights);
dfs(r, COLS - 1, atl, heights);
}
vector<vector<int>> res;
for (int r = 0; r < ROWS; ++r) {
for (int c = 0; c < COLS; ++c) {
if (pac[r][c] && atl[r][c]) {
res.push_back({r, c});
}
}
}
return res;
}
private:
void dfs(int r, int c, vector<vector<bool>>& ocean, vector<vector<int>>& heights) {
ocean[r][c] = true;
for (auto [dr, dc] : directions) {
int nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < heights.size() && nc >= 0 && nc < heights[0].size() && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
dfs(nr, nc, ocean, heights);
}
}
}
};
Java
public class Solution {
private int[][] directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int ROWS = heights.length, COLS = heights[0].length;
boolean[][] pac = new boolean[ROWS][COLS];
boolean[][] atl = new boolean[ROWS][COLS];
for (int c = 0; c < COLS; c++) {
dfs(0, c, pac, heights);
dfs(ROWS - 1, c, atl, heights);
}
for (int r = 0; r < ROWS; r++) {
dfs(r, 0, pac, heights);
dfs(r, COLS - 1, atl, heights);
}
List<List<Integer>> res = new ArrayList<>();
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) { if (pac[r][c] && atl[r][c]) { res.add(Arrays.asList(r, c)); } } } return res; } private void dfs(int r, int c, boolean[][] ocean, int[][] heights) { ocean[r][c] = true; for (int[] d : directions) { int nr = r + d[0], nc = c + d[1]; if (nr >= 0 && nr < heights.length && nc >= 0 && nc < heights[0].length && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
dfs(nr, nc, ocean, heights);
}
}
}
}
Python
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
ROWS, COLS = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, visit, prevHeight):
if ((r, c) in visit or
r < 0 or c < 0 or
r == ROWS or c == COLS or
heights[r][c] < prevHeight
):
return
visit.add((r, c))
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])
for c in range(COLS):
dfs(0, c, pac, heights[0][c])
dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])
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
JavaScript
]class Solution {
/**
* @param {number[][]} heights
* @return {number[][]}
*/
pacificAtlantic(heights) {
let ROWS = heights.length, COLS = heights[0].length;
let pac = Array.from({ length: ROWS }, () =>
Array(COLS).fill(false));
let atl = Array.from({ length: ROWS }, () =>
Array(COLS).fill(false));
const dfs = (r, c, ocean) => {
ocean[r][c] = true;
let directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let [dr, dc] of directions) {
let nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < ROWS && nc >= 0 &&
nc < COLS && !ocean[nr][nc] && heights[nr][nc] >= heights[r][c]) {
dfs(nr, nc, ocean);
}
}
}
for (let c = 0; c < COLS; c++) {
dfs(0, c, pac);
dfs(ROWS - 1, c, atl);
}
for (let r = 0; r < ROWS; r++) {
dfs(r, 0, pac);
dfs(r, COLS - 1, atl);
}
let res = [];
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (pac[r][c] && atl[r][c]) {
res.push([r, c]);
}
}
}
return res;
}
}
