prep-coding/leetcode/GardenNoAdj.java at master · tushar-sharma/prep-coding · 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
/**
 * https://leetcode.com/problems/flower-planting-with-no-adjacent
 *
 * Test Cases :
 *
 *
 5
 [[4,5],[4,3],[2,3],[3,5],[2,4]]

 4
 [[1,2],[3,4]]

 5
 [[4,1],[4,2],[4,3],[2,5],[1,2],[1,5]]

 8
 [[7,4],[3,7],[1,5],[5,4],[7,1],[3,1],[4,3],[6,5]]

 8
 [[1,7],[5,4],[2,8],[7,5],[2,4],[2,7],[4,3],[5,1],[3,1]]
 */
class Solution {

    //adjacenyList
    //it maps vertex to the list of connected vertices
    Map<Integer, List<Integer>> adjacencyList = new HashMap<>();

    public  void addEdges(int[][] paths) {

        for (int i = 0; i < paths.length; i++) {

            if (adjacencyList.containsKey(paths[i][0])) {

                List<Integer> updatedEdges = adjacencyList.get(paths[i][0]);
                updatedEdges.add(paths[i][1]); //returns true
                adjacencyList.put(paths[i][0],
                                  updatedEdges);

            } else {
                List<Integer> updatedEdges = new ArrayList<>();
                updatedEdges.add(paths[i][1]);
                adjacencyList.put(paths[i][0],
                                 updatedEdges);
            }

            if (adjacencyList.containsKey(paths[i][1])) {

                List<Integer> updatedEdges = adjacencyList.get(paths[i][1]);
                updatedEdges.add(paths[i][0]); //returns true
                adjacencyList.put(paths[i][1],
                                  updatedEdges);

            } else {
                List<Integer> updatedEdges = new ArrayList<>();
                updatedEdges.add(paths[i][0]);
                adjacencyList.put(paths[i][1],
                                 updatedEdges);
            }
        }

    }

    /*
    Since it's bidirectional
    outEdges = inEdges
    */
    public List<Integer> outEdges(int n) {
        return adjacencyList.get(n);
    }


    public int[] gardenNoAdj(int N, int[][] paths) {

        if (N <= 0) {
            return new int[]{};
        } else if (N == 1) {
            return new int[]{1};
        }

        if (paths.length == 0) {
            int[] ret = new int[N];
            Arrays.fill(ret, 1);
            return ret;
        }


        addEdges(paths);
        int[] output = new int[N];
        int gardenType = 1;

        int index = 0;

        for (int garden = 1; garden <= N; garden++) {

            List<Integer> edges = outEdges(garden);

            if (edges == null){
                output[index++] = 1;
                //index++;
                continue;
            }

            Set<Integer> possibleType = new HashSet<>();

            for (Integer edge : edges) {
                possibleType.add(output[edge - 1]);
            }

            for (int i = 1; i <= 4; i++){
                if (!possibleType.contains(i)) {
                    gardenType = i;
                    break;

                }

            }

            output[index++] = gardenType;

        }

        return output;

    }
}