Pacific Atlantic Water Flow
There is a matrix of m x n cells, and each cell has a certain height. Water can flow from a cell to its adjacent cells (up, down, left, right) if the adjacent cell has a higher or equal height. There are two oceans: the Pacific Ocean and the Atlantic Ocean. The Pacific Ocean is on the left and top sides of the matrix, and the Atlantic Ocean is on the right and bottom sides. A cell can flow to both oceans if there is a path from the cell to both the Pacific Ocean and the Atlantic Ocean. Find all cells that can flow to both oceans.
Constraints:
- m == heights.length
- n == heights[i].length
- 1 <= m, n <= 200
- 0 <= heights[i][j] <= 10^5
Examples:
Input: [[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 cells that can flow to both oceans are: (0,4), (1,3), (1,4), (2,2), (3,0), (3,1), (4,0).
Solutions
Depth-First Search
The solution uses depth-first search to find all cells that can flow to both oceans. It starts by initializing two 2D arrays, pacific and atlantic, to keep track of the cells that can flow to the Pacific Ocean and the Atlantic Ocean, respectively. Then, it performs DFS from the cells on the borders of the matrix to mark the cells that can flow to the corresponding ocean. Finally, it iterates through the matrix to find the cells that can flow to both oceans and adds them to the result list.
class Solution {
public: vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<vector<bool>> pacific(m, vector<bool>(n, false)), atlantic(m, vector<bool>(n, false));
dfs(pacific, heights, 0, 0, INT_MIN);
dfs(pacific, heights, 0, n-1, INT_MIN);
dfs(atlantic, heights, m-1, 0, INT_MIN);
dfs(atlantic, heights, m-1, n-1, INT_MIN);
for (int i = 0;
i < m;
i++) {
dfs(pacific, heights, i, 0, heights[i][0]);
dfs(atlantic, heights, i, n-1, heights[i][n-1]);
}
for (int j = 0;
j < n;
j++) {
dfs(pacific, heights, 0, j, heights[0][j]);
dfs(atlantic, heights, m-1, j, heights[m-1][j]);
}
vector<vector<int>> result;
for (int i = 0;
i < m;
i++) {
for (int j = 0;
j < n;
j++) {
if (pacific[i][j] && atlantic[i][j]) {
vector<int> list;
list.push_back(i);
list.push_back(j);
result.push_back(list);
}
}
}
return result;
}
private: void dfs(vector<vector<bool>>& visited, vector<vector<int>>& heights, int i, int j, int prevHeight) {
if (i < 0 || i >= heights.size() || j < 0 || j >= heights[0].size() || visited[i][j] || heights[i][j] < prevHeight) return;
visited[i][j] = true;
dfs(visited, heights, i-1, j, heights[i][j]);
dfs(visited, heights, i+1, j, heights[i][j]);
dfs(visited, heights, i, j-1, heights[i][j]);
dfs(visited, heights, i, j+1, heights[i][j]);
}
}
;Follow-up:
Can you optimize the solution to use less space?
