# 1042. Flower Planting With No Adjacent



````java
```java
class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        int[] result = new int[n];
        Arrays.fill(result, 1); // draw one color first

        boolean stop = false;
        while (!stop) {
            stop = true;
            for (int[] path : paths) {
                int u = Math.min(path[0]-1, path[1]-1);
                int v = Math.max(path[0]-1, path[1]-1);

                if (result[u] == result[v]) { // same pattern to change color
                    stop = false;
                    result[u] = getNextColor(result[v]);
                }
            }
        }
        return result;
    }
    private int getNextColor(int c) {
        return c == 4 ? 1 : c+1;
    }
}

```
````



### use set

result is the color we used for result, so when we deal this next node, we can exclude the color we used before.

````java
```java
class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        Map<Integer, List<Integer>> graph = buildGrpah(paths);
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            Set<Integer> used = new HashSet<>(Arrays.asList(1,2,3,4));
            
            if (graph.containsKey(i)) {
                for (int next : graph.get(i)) { // remove neighbor used color
                    if (used.contains(result[next])) { // result[] default is 0, so if not used, won't remove any color
                        used.remove(result[next]);
                    }
                }
            }

            for (int v : used) { // set to current node
                result[i] = v;
                break;
            }
            
        }
        return result;
    }
    private Map<Integer, List<Integer>> buildGrpah(int[][] paths) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] path : paths) {
            graph.putIfAbsent(path[0]-1, new ArrayList<>());
            graph.get(path[0]-1).add(path[1]-1);

            graph.putIfAbsent(path[1]-1, new ArrayList<>());
            graph.get(path[1]-1).add(path[0]-1);
        }
        return graph;
    }
}
```
````
