Notice carefully that the questions states
Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.
We will reverse this idea of water flowing to the ocean and instead think of water flowing from the ocean (this enables us to perform DFS as discussed below). Clearly, the condition mentioned in the question reverses. Now, water from ocean can flow from a cell to another one if height is equal or higher.
The idea is to perform a Depth First Search (DFS) from all positions adjacent to the Pacific ocean to identify the cells which will receive water from the Pacific Ocean. We can move in all four directions during the DFS but we have to ensure that the condition on height is satisfied. Similarly, we will perform another DFS from all positions adjacent to the Atlantic ocean and identify the cells which will receive water from the Atlantic Ocean.
The cells which can receive water from both the oceans will be our answer.
class Solution {
public:
vector<int> offset = {0, 1, 0, -1, 0};
vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
vector<vector<int>> res;
int m = matrix.size();
if (m == 0)
return res;
int n = matrix[0].size();
if (n == 0)
return res;
vector<vector<bool>> pacific(m, vector<bool>(n));
vector<vector<bool>> atlantic(m, vector<bool>(n));
for (int i = 0; i < m; i++) {
dfs(matrix, pacific, i, 0);
dfs(matrix, atlantic, i, n-1);
}
for (int j = 0; j < n; j++) {
dfs(matrix, pacific, 0, j);
dfs(matrix, atlantic, m-1, j);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (pacific[i][j] && atlantic[i][j])
res.push_back({i,j});
}
}
return res;
}
bool outOfBounds(int row, int col, int m, int n) {
return row < 0 || col < 0 || row > m -1 || col > n -1;
}
void dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int i, int j) {
int m = matrix.size();
int n = matrix[0].size();
visited[i][j] = true;
for (int k =1 ; k<offset.size(); k++){
int row = i + offset[k], col = j + offset[k-1] ;
if(!outOfBounds(row, col, m, n) && !visited[row][col] && matrix[row][col] >= matrix[i][j])
dfs(matrix, visited, row, col);
}
}
};
Time complexity: O(n*n) as each position is visited at most once
Notice that I use an “offset” vector above. It’s a neat trick for going to all four directions while performing DFS so that you do not have to hardcode it each time. If you are at position {r,c}, {r+offset[i], c+offset[i-1]} where i>=1 gives you all four directions. i=1: down, i=2: right, i=3: up, i=4: left.