This approach involves performing a DFS from the cells adjacent to the Pacific and Atlantic oceans separately to determine reachable cells for each ocean and then finding their intersection.
The Pacific Ocean can be reached from any cell on the top row or leftmost column. Similarly, the Atlantic Ocean can be reached from any cell on the bottom row or rightmost column. We perform DFS from these boundary cells to mark all cells that can flow into the corresponding ocean. Finally, the intersection of these two sets gives cells that can reach both oceans.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is processed once for each ocean.
Space Complexity: O(m * n), as sets used to keep track of visited cells for both oceans.
1import java.util.*;
2
3public class Solution {
4 private void dfs(int[][] heights, boolean[][] reach, int row, int col, int prevHeight) {
5 int m = heights.length, n = heights[0].length;
6 if (row < 0 || row >= m || col < 0 || col >= n || reach[row][col] || heights[row][col] < prevHeight) return;
7
8 reach[row][col] = true;
9 dfs(heights, reach, row + 1, col, heights[row][col]);
10 dfs(heights, reach, row - 1, col, heights[row][col]);
11 dfs(heights, reach, row, col + 1, heights[row][col]);
12 dfs(heights, reach, row, col - 1, heights[row][col]);
13 }
14
15 public List<List<Integer>> pacificAtlantic(int[][] heights) {
16 if (heights == null || heights.length == 0) return Collections.emptyList();
17
18 int m = heights.length, n = heights[0].length;
19 boolean[][] pacific = new boolean[m][n];
20 boolean[][] atlantic = new boolean[m][n];
21
22 for (int i = 0; i < m; i++) {
23 dfs(heights, pacific, i, 0, heights[i][0]);
24 dfs(heights, atlantic, i, n - 1, heights[i][n - 1]);
25 }
26
27 for (int j = 0; j < n; j++) {
28 dfs(heights, pacific, 0, j, heights[0][j]);
29 dfs(heights, atlantic, m - 1, j, heights[m - 1][j]);
30 }
31
32 List<List<Integer>> result = new ArrayList<>();
33 for (int i = 0; i < m; i++) {
34 for (int j = 0; j < n; j++) {
35 if (pacific[i][j] && atlantic[i][j]) {
36 result.add(Arrays.asList(i, j));
37 }
38 }
39 }
40 return result;
41 }
42}The Java solution implements the same DFS logic. It uses auxiliary 2D boolean arrays to mark reachability for Pacific and Atlantic oceans. DFS is performed from border cells as described earlier.
Finally, cells reachable from both oceans are collected into the result list.
Instead of DFS, we can use BFS to achieve a similar result. This involves starting from the ocean-bordering cells and performing a level-order traversal to mark reachable cells, iteratively checking neighbors in a queue-based manner. BFS might be preferred in scenarios where recursion depth in DFS isn't ideal or could lead to stack overflow.
The idea is to initiate BFS from each ocean's boundary simultaneously, progressively marking each reachable cell, and determining intersecting positions for final results.
Time Complexity: O(m * n), where BFS is performed from a subset of cells and checks neighbors iteratively.
Space Complexity: O(m * n), contingent upon queue operations and reachability matrices.
1#include <bits/stdc++.h>
2using namespace std;
3
4vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
5 if (heights.empty() || heights[0].empty()) return {};
6 int m = heights.size(), n = heights[0].size();
7 vector<vector<bool>> pacific(m, vector<bool>(n, false));
8 vector<vector<bool>> atlantic(m, vector<bool>(n, false));
9 queue<pair<int, int>> pacQueue, atlQueue;
10
11 for (int i = 0; i < m; ++i) {
12 pacQueue.push({i, 0});
13 atlQueue.push({i, n-1});
14 }
15
16 for (int j = 0; j < n; ++j) {
17 pacQueue.push({0, j});
18 atlQueue.push({m-1, j});
19 }
20
21 auto bfs = [&](queue<pair<int, int>>& q, vector<vector<bool>>& ocean) {
22 vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
23 while (!q.empty()) {
24 auto [x, y] = q.front(); q.pop();
25 ocean[x][y] = true;
26 for (auto& [dx, dy] : directions) {
27 int nx = x + dx, ny = y + dy;
28 if (nx >= 0 && nx < m && ny >= 0 && ny < n && !ocean[nx][ny] && heights[nx][ny] >= heights[x][y]) {
29 q.push({nx, ny});
30 ocean[nx][ny] = true;
31 }
32 }
33 }
34 };
35
36 bfs(pacQueue, pacific);
37 bfs(atlQueue, atlantic);
38
39 vector<vector<int>> result;
40 for (int i = 0; i < m; ++i) {
41 for (int j = 0; j < n; ++j) {
42 if (pacific[i][j] && atlantic[i][j]) {
43 result.push_back({i, j});
44 }
45 }
46 }
47 return result;
48}In C++, we implement BFS using queues and lambda function `bfs` for processing. Cells reachable from both oceans are tracked using boolean matrices, similar to other languages.
This approach leverages pair and queue operations to iteratively mark cells.