417. Pacific Atlantic Water Flow

,

BFS

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
51
52
53
54
55
56
57
58
class Solution {
    private static final int[][] DIRECTIONS = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;

        List<List<Integer>> cellList = new ArrayList<>();

        Queue<int[]> queue1 = new LinkedList<>();
        Queue<int[]> queue2 = new LinkedList<>();

        boolean[][] visited1 = new boolean[m][n];
        boolean[][] visited2 = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    queue1.offer(new int[]{i, j});
                    visited1[i][j] = true;
                }
                if (i == m - 1 || j == n - 1) {
                    queue2.offer(new int[]{i, j});
                    visited2[i][j] = true;
                }
            }
        }

        bfs(queue1, heights, visited1);
        bfs(queue2, heights, visited2);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited1[i][j] && visited2[i][j]) {
                    cellList.add(Arrays.asList(i, j));
                }
            }
        }

        return cellList;
    }

    private void bfs(Queue<int[]> queue, int[][] heights, boolean[][] visited) {
        int m = heights.length, n = heights[0].length;

        while (!queue.isEmpty()) {
            int[] cell = queue.poll();

            for (int[] direction : DIRECTIONS) {
                int i = cell[0] + direction[0], j = cell[1] + direction[1];
                if (i >= 0 && i < m && j >= 0 && j < n && !visited[i][j] && heights[i][j] >= heights[cell[0]][cell[1]]) {
                    queue.offer(new int[]{i, j});
                }
            }

            visited[cell[0]][cell[1]] = true;
        }
    }
}

DFS

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
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> resultList = new ArrayList<>();

        int m = heights.length, n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            dfs(heights, pacific, i, 0, m, n);
            dfs(heights, atlantic, i, n - 1, m, n);
        }
        for (int j = 0; j < n; j++) {
            dfs(heights, pacific, 0, j, m, n);
            dfs(heights, atlantic, m - 1, j, m, n);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacific[i][j] && atlantic[i][j]) {
                    resultList.add(Arrays.asList(i, j));
                }
            }
        }

        return resultList;
    }

    private void dfs(int[][] heights, boolean[][] flags, int i, int j, int m, int n) {
        if (flags[i][j]) {
            return;
        }

        flags[i][j] = true;
        
        if (i > 0 && heights[i - 1][j] >= heights[i][j]) {
            dfs(heights, flags, i - 1, j, m, n);
        }
        if (i < m - 1 && heights[i + 1][j] >= heights[i][j]) {
            dfs(heights, flags, i + 1, j, m, n);
        }
        if (j > 0 && heights[i][j - 1] >= heights[i][j]) {
            dfs(heights, flags, i, j - 1, m, n);
        }
        if (j < n - 1 && heights[i][j + 1] >= heights[i][j]) {
            dfs(heights, flags, i, j + 1, m, n);
        }
    }
}

References

417. Pacific Atlantic Water Flow