Skip to content

417. Pacific Atlantic Water Flow

🔗 Source

Intuition

Giving you a 2-d metrix, you need to find all entries on the path to the "edge" of this metrix

Approach

Perform DFS on every entry on the edge of the metrix. And traverse the metrix to find all visited entries.

  • Firstly, we creat a Pacific visited metrix and an Atlantic visit metrix.
  • Secondly, we perform dfs on each edge and update our two visit metrices.
    • For entries where water is able to flow to the Pacific Ocean, perform DFS on each entry of the top and left side.
    • For entries where water is able to flow to the Atlantic Ocean, perform DFS on each entry of the bottom and right side.
  • After we update our two visit metrices, we traverse them at same time to find entries whose rain water can flow to both the Pacific and Atlantic oceans.

Complexity

  • Time complexity: \(O(R\times C)\), where \(R\) is the number of rows and \(C\) is the number of columns
  • Space complexity: \(O(R\times C)\), as we creat two visit metrices.

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
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int row = heights.length;
        int col = heights[0].length;
        boolean[][] pac = new boolean[row][col];
        boolean[][] atl = new boolean[row][col];
        for (int j = 0; j < col; j++) {
            dfs(0, j, row, col, heights[0][j], heights, pac);
            dfs(row - 1, j, row, col, heights[row - 1][j], heights, atl);
        }
        for (int i = 0; i < row; i++) {
            dfs(i, 0, row, col, heights[i][0], heights, pac);
            dfs(i, col - 1, row, col, heights[i][col - 1], heights, atl);
        }
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (pac[i][j] && atl[i][j]) {
                    res.add(Arrays.asList(i,j));
                }
            }
        }
        return res;
    }

    private void dfs(int x, int y, int row, int col, int prev,
                     int[][] height, boolean[][] visit) {
        if (x < 0 || x >= row || y < 0 || y >= col || visit[x][y] || prev > height[x][y]) {
            return;
        }
        visit[x][y] = true;
        dfs(x + 1, y, row, col, height[x][y], height, visit);
        dfs(x, y + 1, row, col, height[x][y], height, visit);
        dfs(x - 1, y, row, col, height[x][y], height, visit);
        dfs(x, y - 1, row, col, height[x][y], height, visit);
    }
}