Pacific Atlantic Water Flow

110.1k
0

Given an R×C matrix heights, where each cell stores terrain height, return all coordinates from which water can flow to both the Pacific Ocean and the Atlantic Ocean.

The Pacific Ocean touches the top and left borders. The Atlantic Ocean touches the bottom and right borders. Water can move from a cell to a neighboring cell in four directions only when the neighboring height is less than or equal to the current height.

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: Each listed cell has at least one non-increasing path toward the Pacific border and at least one non-increasing path toward the Atlantic border.

Example 2

Input: heights = [[1]]

Output: [[0,0]]

Explanation: The single cell touches both oceans through matrix borders.

Brute Force Approach

A separate DFS begins from every grid cell and follows natural water flow toward neighboring cells having lower or equal heights. Pacific and Atlantic flags record whether a traversal reaches a border belonging to each ocean.

A fresh visited matrix prevents cycles through equal-height cells. Repeated exploration from every starting cell guarantees correctness but produces a high overall time complexity.

Algorithm

  • Initialize an empty answer list for coordinates capable of reaching both oceans.

  • Traverse every cell using an outer loop for rows and an inner loop for columns, treating each cell as an independent source.

  • Create a fresh visited matrix and two reachability flags for every source, keeping each DFS independent.

  • Mark the current DFS cell as visited and update the Pacific or Atlantic flag after reaching a corresponding border.

  • Explore every unvisited orthogonal neighbor having a lower or equal height, following natural water flow.

  • Add the source coordinate after both ocean flags become true.

  • Return the complete coordinate list after all grid cells have been tested.

Dry Run

pacific

pacific

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Explores downhill or equal-height paths from one cell.
void search(int row, int col, vector<vector<int>>& heights,
vector<vector<int>>& visited, bool& pacific, bool& atlantic) {
int rows = heights.size();
int cols = heights[0].size();
vector<int> deltaRow = {-1, 1, 0, 0};
vector<int> deltaCol = {0, 0, -1, 1};
// Mark the current cell before exploring neighbors.
visited[row][col] = 1;
// Touching top or left border means Pacific is reachable.
if (row == 0 || col == 0) {
pacific = true;
}
// Touching bottom or right border means Atlantic is reachable.
if (row == rows - 1 || col == cols - 1) {
atlantic = true;
}
// Stop early after both oceans are reached.
if (pacific && atlantic) {
return;
}
// Explore all four directions.
for (int direction = 0; direction < 4; direction++) {
int nextRow = row + deltaRow[direction];
int nextCol = col + deltaCol[direction];
// Check if the next cell is inside the grid.
if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols) {
// Water can flow only to lower or equal-height unvisited cells.
if (visited[nextRow][nextCol] == 0 && heights[nextRow][nextCol] <= heights[row][col]) {
search(nextRow, nextCol, heights, visited, pacific, atlantic);
}
}
}
}
public:
// Returns every coordinate capable of reaching both oceans.
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int rows = heights.size();
int cols = heights[0].size();
vector<vector<int>> answer;
// Test every cell as an independent water source.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
vector<vector<int>> visited(rows, vector<int>(cols, 0));
bool pacific = false;
bool atlantic = false;
// Search all downhill paths from the current cell.
search(row, col, heights, visited, pacific, atlantic);
// Store cells that can reach both oceans.
if (pacific && atlantic) {
answer.push_back({row, col});
}
}
}
// Return all valid coordinates.
return answer;
}
};
// Prints coordinates in matrix form.
void printCoordinates(vector<vector<int>>& coordinates) {
cout << "[";
for (int index = 0; index < coordinates.size(); index++) {
if (index > 0) {
cout << ",";
}
cout << "[" << coordinates[index][0] << "," << coordinates[index][1] << "]";
}
cout << "]";
}
// Driver code.
int main() {
vector<vector<int>> 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}
};
Solution sol;
vector<vector<int>> answer = sol.pacificAtlantic(heights);
printCoordinates(answer);
return 0;
}

Complexity Analysis

Time Complexity: O((R×C)²), where R and C are the grid dimensions; each of the R×C cells can start a DFS covering the entire grid.

Space Complexity: O(R×C), where the visited matrix and recursive DFS stack can each contain up to R×C cells during one search.

Optimal Approach 1

Reverse DFS begins from the borders of both oceans and moves toward cells having greater or equal heights. Reverse reachability from an ocean confirms a natural downhill or equal-height route from the reached cell back to the ocean.

Separate Pacific and Atlantic matrices record reachability. An outer row loop and inner column loop collect coordinates marked in both matrices.

Algorithm

  • Initialize separate Pacific and Atlantic reachability matrices.

  • Start Pacific DFS from all top-border and left-border cells.

  • Start Atlantic DFS from all bottom-border and right-border cells.

  • Mark each current cell before exploring neighbors, preventing repeated DFS visits.

  • Move toward every unvisited neighbor having a greater or equal height, reversing natural water flow.

  • Scan the grid and add every coordinate marked in both reachability matrices.

  • Return the complete coordinate list.

Dry Run

pacific reverse dfs

pacific reverse dfs

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Marks cells reachable from one ocean using reverse DFS.
void dfs(int row, int col, vector<vector<int>>& heights, vector<vector<int>>& reachable) {
int rows = heights.size();
int cols = heights[0].size();
vector<int> deltaRow = {-1, 1, 0, 0};
vector<int> deltaCol = {0, 0, -1, 1};
// Mark the current cell as reachable.
reachable[row][col] = 1;
// Explore all four directions.
for (int direction = 0; direction < 4; direction++) {
int nextRow = row + deltaRow[direction];
int nextCol = col + deltaCol[direction];
// Check if the next cell is inside the grid.
if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols) {
// Move only to unvisited cells with greater or equal height.
if (reachable[nextRow][nextCol] == 0 && heights[nextRow][nextCol] >= heights[row][col]) {
dfs(nextRow, nextCol, heights, reachable);
}
}
}
}
// Starts DFS only from an unmarked border cell.
void startDfs(int row, int col, vector<vector<int>>& heights, vector<vector<int>>& reachable) {
// Skip the cell if already marked.
if (reachable[row][col] == 1) {
return;
}
// Start reverse DFS from the border cell.
dfs(row, col, heights, reachable);
}
public:
// Returns every coordinate capable of reaching both oceans.
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int rows = heights.size();
int cols = heights[0].size();
vector<vector<int>> pacific(rows, vector<int>(cols, 0));
vector<vector<int>> atlantic(rows, vector<int>(cols, 0));
// Start reverse DFS from left and right borders.
for (int row = 0; row < rows; row++) {
startDfs(row, 0, heights, pacific);
startDfs(row, cols - 1, heights, atlantic);
}
// Start reverse DFS from top and bottom borders.
for (int col = 0; col < cols; col++) {
startDfs(0, col, heights, pacific);
startDfs(rows - 1, col, heights, atlantic);
}
vector<vector<int>> answer;
// Collect cells reachable from both oceans.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (pacific[row][col] == 1 && atlantic[row][col] == 1) {
answer.push_back({row, col});
}
}
}
// Return all valid coordinates.
return answer;
}
};
// Prints coordinates in matrix form.
void printCoordinates(vector<vector<int>>& coordinates) {
cout << "[";
for (int index = 0; index < coordinates.size(); index++) {
if (index > 0) {
cout << ",";
}
cout << "[" << coordinates[index][0] << "," << coordinates[index][1] << "]";
}
cout << "]";
}
// Driver code.
int main() {
vector<vector<int>> 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}
};
Solution sol;
vector<vector<int>> answer = sol.pacificAtlantic(heights);
printCoordinates(answer);
return 0;
}

Complexity Analysis

Time Complexity: O(R×C), where R and C are the grid dimensions; each ocean traversal visits every cell at most once.

Space Complexity: O(R×C), where two reachability matrices and the recursive DFS stack store up to R×C cells.

Optimal Approach 2

Reverse BFS performs multi-source traversal from all Pacific and Atlantic border cells. Separate queues expand reachability from both oceans without recursive calls.

A guarded border-insertion helper marks a cell and enqueues the coordinate only after finding an unmarked state. Every corner therefore enters the corresponding ocean queue exactly once. Reverse traversal moves toward neighboring cells having greater or equal heights.

Algorithm

  • Initialize separate reachability matrices and queues for both oceans.

  • Add Pacific top-border and left-border cells through a guarded insertion helper.

  • Add Atlantic bottom-border and right-border cells through the same guarded insertion helper.

  • Process both queues independently, removing cells in multi-source BFS order.

  • Mark and enqueue every unvisited neighbor having a greater or equal height.

  • Scan the grid and add every coordinate marked in both reachability matrices.

  • Return the complete coordinate list.

Dry Run

pacific reverse bfs

pacific reverse bfs

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Add one border cell exactly once for one ocean.
void addCell(int row, int col, vector<vector<int>>& reachable, queue<pair<int, int>>& cells) {
// Skip a cell already added to the ocean queue.
if (reachable[row][col] == 1) {
return;
}
// Mark before queue insertion to prevent duplicates.
reachable[row][col] = 1;
cells.push({row, col});
}
// Mark every cell reachable from one ocean using reverse BFS.
void bfs(queue<pair<int, int>>& cells, vector<vector<int>>& heights, vector<vector<int>>& reachable) {
int rows = heights.size();
int cols = heights[0].size();
vector<int> deltaRow = {-1, 1, 0, 0};
vector<int> deltaCol = {0, 0, -1, 1};
// Process all cells in multi-source BFS order.
while (!cells.empty()) {
auto [row, col] = cells.front();
cells.pop();
// Explore all four orthogonal neighbors.
for (int direction = 0; direction < 4; direction++) {
int nextRow = row + deltaRow[direction];
int nextCol = col + deltaCol[direction];
// Check if the next cell is inside the grid.
if (nextRow >= 0 && nextCol >= 0 && nextRow < rows && nextCol < cols) {
// Move in reverse flow direction toward higher cells.
if (reachable[nextRow][nextCol] == 0 && heights[nextRow][nextCol] >= heights[row][col]) {
reachable[nextRow][nextCol] = 1;
cells.push({nextRow, nextCol});
}
}
}
}
}
public:
// Return every coordinate capable of reaching both oceans.
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
// Handle an empty grid safely.
if (heights.empty() || heights[0].empty()) {
return {};
}
int rows = heights.size();
int cols = heights[0].size();
vector<vector<int>> pacific(rows, vector<int>(cols, 0));
vector<vector<int>> atlantic(rows, vector<int>(cols, 0));
queue<pair<int, int>> pacificQueue;
queue<pair<int, int>> atlanticQueue;
// Add Pacific left border and Atlantic right border.
for (int row = 0; row < rows; row++) {
addCell(row, 0, pacific, pacificQueue);
addCell(row, cols - 1, atlantic, atlanticQueue);
}
// Add Pacific top border and Atlantic bottom border.
for (int col = 0; col < cols; col++) {
addCell(0, col, pacific, pacificQueue);
addCell(rows - 1, col, atlantic, atlanticQueue);
}
// Mark reverse-reachable Pacific cells.
bfs(pacificQueue, heights, pacific);
// Mark reverse-reachable Atlantic cells.
bfs(atlanticQueue, heights, atlantic);
vector<vector<int>> answer;
// Collect cells reachable from both oceans.
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (pacific[row][col] == 1 && atlantic[row][col] == 1) {
answer.push_back({row, col});
}
}
}
// Return all valid coordinates.
return answer;
}
};
// Print coordinates in matrix notation.
void printCoordinates(const vector<vector<int>>& coordinates) {
cout << "[";
for (int index = 0; index < static_cast<int>(coordinates.size()); index++) {
if (index > 0) {
cout << ",";
}
cout << "[" << coordinates[index][0] << "," << coordinates[index][1] << "]";
}
cout << "]\n";
}
// Driver code.
int main() {
vector<vector<int>> heights = {
{1, 2, 2, 3, 5},
{3, 2, 3, 4, 4},
{2, 4, 5, 3, 1},
{6, 7, 1, 4, 5},

Complexity Analysis

Time Complexity: O(R×C), where R and C are the grid dimensions; each cell enters each ocean queue at most once.

Space Complexity: O(R×C), where two reachability matrices and two queues collectively store a number of cells proportional to R×C.

Interview follow-up Questions

Ocean-start traversal avoids repeated searches and marks all cells able to flow to an ocean in one pass.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: DisjointSet(int...

89.1k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Graph

Network Delay Time Using Dijkstra's Algorithm

A network contains n nodes labeled from 1 to n . Each directed edge [u,v,w] means a signal needs w time units to travel from node u to node v . A signal starts from node k . Return th...

81.2k
Comments0