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.
1def pacificAtlantic(heights):
2 if not heights or not heights[0]:
3 return []
4
5 def dfs(x, y, reach):
6 reach.add((x, y))
7 for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]: # directions
8 nx, ny = x + dx, y + dy
9 if 0 <= nx < m and 0 <= ny < n and (nx, ny) not in reach and heights[nx][ny] >= heights[x][y]:
10 dfs(nx, ny, reach)
11
12 m, n = len(heights), len(heights[0])
13 pacific_reach, atlantic_reach = set(), set()
14
15 for i in range(m):
16 dfs(i, 0, pacific_reach) # Pacific Ocean
17 dfs(i, n-1, atlantic_reach) # Atlantic Ocean
18
19 for j in range(n):
20 dfs(0, j, pacific_reach) # Pacific Ocean
21 dfs(m-1, j, atlantic_reach) # Atlantic Ocean
22
23 return list(pacific_reach & atlantic_reach)The above function defines a DFS method and applies it from each pacific and atlantic border cell. For pacific, it applies DFS from top row and left column, while for atlantic, it's from bottom row and right column.
DFS explores in four directions, making recursive calls when conditions are satisfied, and keeps track of reachable cells using sets.
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.
1import java.util.*;
2
3public class Solution {
4 public List<List<Integer>> pacificAtlantic(int[][] heights) {
5 if (heights == null || heights.length == 0) return Collections.emptyList();
6
7 int m = heights.length, n = heights[0].length;
8 boolean[][] pacific = new boolean[m][n];
9 boolean[][] atlantic = new boolean[m][n];
10
11 Queue<int[]> pacificQueue = new LinkedList<>();
12 Queue<int[]> atlanticQueue = new LinkedList<>();
13
14 for (int i = 0; i < m; i++) {
15 pacificQueue.offer(new int[] { i, 0 });
16 atlanticQueue.offer(new int[] { i, n - 1 });
17 }
18 for (int j = 0; j < n; j++) {
19 pacificQueue.offer(new int[] { 0, j });
20 atlanticQueue.offer(new int[] { m - 1, j });
21 }
22
23 bfs(heights, pacific, pacificQueue);
24 bfs(heights, atlantic, atlanticQueue);
25
26 List<List<Integer>> result = new ArrayList<>();
27 for (int i = 0; i < m; i++) {
28 for (int j = 0; j < n; j++) {
29 if (pacific[i][j] && atlantic[i][j]) {
30 result.add(Arrays.asList(i, j));
31 }
32 }
33 }
34
35 return result;
36 }
37
38 private void bfs(int[][] heights, boolean[][] ocean, Queue<int[]> queue) {
39 int m = heights.length, n = heights[0].length;
40 int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
41 while (!queue.isEmpty()) {
42 int[] cell = queue.poll();
43 int x = cell[0], y = cell[1];
44 ocean[x][y] = true;
45
46 for (int[] dir : directions) {
47 int nx = x + dir[0], ny = y + dir[1];
48 if (nx >= 0 && nx < m && ny >= 0 && ny < n && !ocean[nx][ny] && heights[nx][ny] >= heights[x][y]) {
49 queue.offer(new int[] {nx, ny});
50 ocean[nx][ny] = true;
51 }
52 }
53 }
54 }
55}The Java solution applies BFS using queue mechanisms for traversal, where each queue manages cells for Pacific and Atlantic reachability, starting from respective ocean-bordering cells.
Level-order processing enables marking cell paths efficiently, lateral to both DFS and other BFS implementations.