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.
1public class Solution {
2 private void Dfs(int[][] heights, bool[][] reach, int row, int col, int prevHeight) {
3 int m = heights.Length, n = heights[0].Length;
4 if (row < 0 || row >= m || col < 0 || col >= n || reach[row][col] || heights[row][col] < prevHeight) return;
5 reach[row][col] = true;
6 Dfs(heights, reach, row + 1, col, heights[row][col]);
7 Dfs(heights, reach, row - 1, col, heights[row][col]);
8 Dfs(heights, reach, row, col + 1, heights[row][col]);
9 Dfs(heights, reach, row, col - 1, heights[row][col]);
10 }
11
12 public IList<IList<int>> PacificAtlantic(int[][] heights) {
13 if (heights == null || heights.Length == 0) return new List<IList<int>>();
14
15 int m = heights.Length, n = heights[0].Length;
16 bool[][] pacific = new bool[m][];
17 bool[][] atlantic = new bool[m][];
18
19 for (int i = 0; i < m; i++) {
20 pacific[i] = new bool[n];
21 atlantic[i] = new bool[n];
22 }
23
24 for (int i = 0; i < m; i++) {
25 Dfs(heights, pacific, i, 0, heights[i][0]);
26 Dfs(heights, atlantic, i, n - 1, heights[i][n - 1]);
27 }
28
29 for (int j = 0; j < n; j++) {
30 Dfs(heights, pacific, 0, j, heights[0][j]);
31 Dfs(heights, atlantic, m - 1, j, heights[m - 1][j]);
32 }
33
34 IList<IList<int>> result = new List<IList<int>>();
35 for (int i = 0; i < m; i++) {
36 for (int j = 0; j < n; j++) {
37 if (pacific[i][j] && atlantic[i][j]) {
38 result.Add(new List<int>{i, j});
39 }
40 }
41 }
42 return result;
43 }
44}The C# solution also implements a DFS approach similar to other languages. We maintain reachability boolean arrays for both oceans and perform depth-first searches from the boundary cells to mark accessible cells.
Finally, we gather cells reachable by both Atlantic and Pacific 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.
1from collections import deque
2
3def pacificAtlantic(heights):
4 if not heights or not heights[0]:
5 return []
6
7 m, n = len(heights), len(heights[0])
8 pacific = [[False] * n for _ in range(m)]
9 atlantic = [[False] * n for _ in range(m)]
10
11 def bfs(starts, ocean):
12 queue = deque(starts)
13 while queue:
14 x, y = queue.popleft()
15 ocean[x][y] = True
16 for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
17 nx, ny = x + dx, y + dy
18 if 0 <= nx < m and 0 <= ny < n:
19 if not ocean[nx][ny] and heights[nx][ny] >= heights[x][y]:
20 queue.append((nx, ny))
21 ocean[nx][ny] = True
22
23 pacific_starts = [(i, 0) for i in range(m)] + [(0, j) for j in range(n)]
24 atlantic_starts = [(i, n-1) for i in range(m)] + [(m-1, j) for j in range(n)]
25
26 bfs(pacific_starts, pacific)
27 bfs(atlantic_starts, atlantic)
28
29 return [[x, y] for x in range(m) for y in range(n) if pacific[x][y] and atlantic[x][y]]This function uses a deque to implement BFS from both Pacific and Atlantic borders. Starting points are defined for each ocean, and a queue processes each cell, enqueuing adjacent cells that retain valid flow conditions.
The results are gathered similarly by intersecting valid Pacific and Atlantic reachable positions.