leetcode-grind/src/graph/PacificAtlanticWaterFlow.java at main · karle0wne/leetcode-grind · GitHub

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
package graph;

import java.util.*;

/**
 * Description: https://leetcode.com/problems/pacific-atlantic-water-flow
 * Difficulty: Medium
 */
public class PacificAtlanticWaterFlow {

    private int[][] directions;

    /**
     * Time complexity: O(m * n)
     * Space complexity: O(m * n)
     */
    public List<List<Integer>> pacificAtlanticOptimalApproach(int[][] heights) {
        directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int[][] pacific = new int[heights.length][heights[0].length];
        int[][] atlantic = new int[heights.length][heights[0].length];

        // start flow from left and right borders
        for (int i = 0; i < heights.length; i++) {
            dfs(heights, pacific, new int[]{i, 0});
            dfs(heights, atlantic, new int[]{i, heights.length - 1});
        }

        // start flow from top and bottom borders
        for (int i = 0; i < heights[0].length; i++) {
            dfs(heights, pacific, new int[]{0, i});
            dfs(heights, atlantic, new int[]{heights[0].length - 1, i});
        }

        // if cell was visited by both flows -> add to the result
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < heights.length; i++) {
            for (int j = 0; j < heights[0].length; j++) {
                if (pacific[i][j] != 0 && atlantic[i][j] != 0) {
                    result.add(List.of(i, j));
                }
            }
        }

        return result;
    }

    private void dfs(int[][] heights, int[][] visited, int[] start) {
        Deque<int[]> stack = new LinkedList<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int[] current = stack.pop();

            if (visited[current[0]][current[1]] == 0) {
                stack.push(current);
                visited[current[0]][current[1]] = 1;

                for (int[] dir : directions) {
                    int x = current[0] + dir[0];
                    int y = current[1] + dir[1];

                    if (x >= 0 && y >= 0 && x < heights.length && y < heights[0].length
                            && visited[x][y] == 0
                            // we're going backwards -> next height should be greater or equal than current
                            && heights[x][y] >= heights[current[0]][current[1]]) {
                        stack.push(new int[]{x, y});
                    }
                }
            } else if (visited[current[0]][current[1]] == 1) {
                visited[current[0]][current[1]] = 2;
            }
        }
    }

    /**
     * Time complexity: O(m^2 * n^2)
     * Space complexity: O(m * n)
     */
    public List<List<Integer>> pacificAtlanticNaiveApproach(int[][] heights) {
        directions = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < heights.length; i++) {
            for (int j = 0; j < heights[0].length; j++) {
                if (canFlowBothWays(heights, new int[]{i, j})) {
                    result.add(List.of(i, j));
                }
            }
        }

        return result;
    }

    private boolean canFlowBothWays(int[][] heights, int[] start) {
        int[][] visited = new int[heights.length][heights[0].length];
        boolean hasPacificPath = false;
        boolean hasAtlanticPath = false;

        Deque<int[]> stack = new LinkedList<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int[] current = stack.pop();

            if (visited[current[0]][current[1]] == 0) {
                visited[current[0]][current[1]] = 1;
                stack.push(current);

                for (int[] dir : directions) {
                    int x = current[0] + dir[0];
                    int y = current[1] + dir[1];

                    if (x < 0 || y < 0) {
                        hasPacificPath = true;
                    } else if (x >= heights.length || y >= heights[0].length) {
                        hasAtlanticPath = true;
                    } else if (visited[x][y] == 0 && heights[x][y] <= heights[current[0]][current[1]]) {
                        stack.push(new int[]{x, y});
                    }

                    if (hasPacificPath && hasAtlanticPath) return true;
                }
            } else if (visited[current[0]][current[1]] == 1) {
                visited[current[0]][current[1]] = 2;
            }
        }

        return false;
    }
}