Problem

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Examples

Example 1:

$$ heights = \begin{array}{|c|c|c|c|c|} \hline 1 & 2 & 2 & 3 & \colorbox{orange}5 \\ \hline 3 & 2 & 3 & \colorbox{orange}4 & \colorbox{orange}4 \\ \hline 2 & 4 & \colorbox{orange}5 & 3 & 1 \\ \hline \colorbox{orange}6 & \colorbox{orange}7 & 1 & 4 & 5 \\ \hline \colorbox{orange}5 & 1 & 1 & 2 & 4 \\ \hline \end{array} $$

1
2

Input: heights = [[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]]

Example 2:

1
2

Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]

Solution

Method 1 - BFS

We can see how many points can water flow to pacific point, and how many points can water flow to atlantic oceans. The intersection of these sets will the answer we want.

We can see first row is adjacent to Pacific ocean and last row is adjacent to Atlantic ocean. Likewise, first column is adjacent to pacific ocean and last column is adjacent to Atlantic ocean.

From these points we do BFS, so that we dont visit the same points again and again.

Approach

Here is the approach:

  • We identify the cells adjacent to the Pacific and Atlantic oceans:
    • Cells in the first row and first column are adjacent to the Pacific Ocean.
    • Cells in the last row and last column are adjacent to the Atlantic Ocean.
  • From these ocean-adjacent cells, we perform BFS to explore all cells reachable by water for that ocean.
  • At the end, the intersection of reachable cells from both oceans gives the desired result.
  • BFS ensures that we visit cells level by level, marking them as visited to avoid redundant visits.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        
        // BFS function to compute reachable cells
        Set<List<Integer>> bfs(List<int[]> starts) {
            Set<List<Integer>> visited = new HashSet<>();
            Queue<int[]> q = new LinkedList<>();
            for (int[] start : starts) {
                q.add(start);
                visited.add(Arrays.asList(start[0], start[1]));
            }
            int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Directions
            
            while (!q.isEmpty()) {
                int[] cell = q.poll();
                for (int[] d : dirs) {
                    int x = cell[0] + d[0], y = cell[1] + d[1];
                    if (x >= 0 && x < m && y >= 0 && y < n && !visited.contains(Arrays.asList(x, y)) && heights[x][y] >= heights[cell[0]][cell[1]]) {
                        visited.add(Arrays.asList(x, y));
                        q.offer(new int[] {x, y});
                    }
                }
            }
            return visited;
        }
        
        // Starting points for Pacific and Atlantic
        List<int[]> pac_starts = new ArrayList<>();
        List<int[]> atl_starts = new ArrayList<>();
        
        for (int i = 0; i < m; i++) {
            pac_starts.add(new int[] {i, 0});
            atl_starts.add(new int[] {i, n - 1});
        }
        for (int j = 0; j < n; j++) {
            pac_starts.add(new int[] {0, j});
            atl_starts.add(new int[] {m - 1, j});
        }
        
        // Find all cells reachable by each ocean
        Set<List<Integer>> pac_reachable = bfs(pac_starts);
        Set<List<Integer>> atl_reachable = bfs(atl_starts);
        
        // Intersection of reachable cells
        pac_reachable.retainAll(atl_reachable);
        
        return new ArrayList<>(pac_reachable);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        
        # BFS function to compute reachable cells
        def bfs(starts: List[List[int]]) -> set:
            visited = set(starts)
            q = deque(starts)
            while q:
                r, c = q.popleft()
                for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):  # Directions (up, right, down, left)
                    x, y = r + dr, c + dc
                    if 0 <= x < m and 0 <= y < n and (x, y) not in visited and heights[x][y] >= heights[r][c]:
                        visited.add((x, y))
                        q.append((x, y))
            return visited

        # Starting points for Pacific and Atlantic
        pac_starts = [(0, j) for j in range(n)] + [(i, 0) for i in range(m)]
        atl_starts = [(m - 1, j) for j in range(n)] + [(i, n - 1) for i in range(m)]
        
        # Find all cells reachable by each ocean
        pac_reachable = bfs(pac_starts)
        atl_reachable = bfs(atl_starts)
        
        # Intersection of reachable cells
        return list(pac_reachable & atl_reachable)

Complexity

  • ⏰ Time complexity: O(m * n) because each cell is visited once for BFS for both oceans.
  • 🧺 Space complexity: O(m * n) to store visited states and queue space.

Method 2 - DFS

We can use the similar approach, but instead use DFS, hence stack.

Approach

  1. Identify Flow Possibility:
    • Water can flow from a higher or equal height to a lower height cell.
    • It starts from cells on the edge of the Pacific (left and top edges) and Atlantic (right and bottom edges).
  2. Reverse Simulation:
    • Instead of simulating water from each cell flowing to the oceans, simulate water flowing inward from the oceans using DFS or BFS.
    • Use two m x n boolean matrices (pac and atl) to keep track of cells that can reach the respective oceans.
  3. Combine Results:
    • After performing two DFS/BFS starting from both oceans, find the intersection of cells that can flow to both oceans (i.e., cells marked True in both matrices).
  4. Implementation Steps:
    • Initialise pac and atl boolean matrices.
    • Perform DFS/BFS for each ocean, starting from its boundary cells.
    • Combine results into a list of coordinates that can flow to both oceans.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        boolean[][] pac = new boolean[m][n];
        boolean[][] atl = new boolean[m][n];
        List<List<Integer>> ans = new ArrayList<>();
        
        for (int i = 0; i < m; i++) {
            dfs(heights, pac, i, 0);
            dfs(heights, atl, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, pac, 0, j);
            dfs(heights, atl, m - 1, j);
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pac[i][j] && atl[i][j]) {
                    List<Integer> cell = new ArrayList<>();
                    cell.add(i);
                    cell.add(j);
                    ans.add(cell);
                }
            }
        }
        return ans;
    }

    private void dfs(int[][] h, boolean[][] ocean, int r, int c) {
        ocean[r][c] = true;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int[] d : dirs) {
            int x = r + d[0], y = c + d[1];
            if (x >= 0 && x < h.length && y >= 0 && y < h[0].length && !ocean[x][y] && h[x][y] >= h[r][c]) {
                dfs(h, ocean, x, y);
            }
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        pac = [[False] * n for _ in range(m)]
        atl = [[False] * n for _ in range(m)]
        ans: List[List[int]] = []
        
        def dfs(h: List[List[int]], ocean: List[List[bool]], r: int, c: int) -> None:
            ocean[r][c] = True
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                x, y = r + dr, c + dc
                if 0 <= x < m and 0 <= y < n and not ocean[x][y] and h[x][y] >= h[r][c]:
                    dfs(h, ocean, x, y)
        
        for i in range(m):
            dfs(heights, pac, i, 0)
            dfs(heights, atl, i, n - 1)
        for j in range(n):
            dfs(heights, pac, 0, j)
            dfs(heights, atl, m - 1, j)
        
        for i in range(m):
            for j in range(n):
                if pac[i][j] and atl[i][j]:
                    ans.append([i, j])
        
        return ans

Complexity

  • ⏰ Time complexity: O(m * n) because each cell can be visited at most twice (once for each ocean).
  • 🧺 Space complexity: O(m * n) for the visited matrices and recursion stack.