Problem statement

https://leetcode.com/problems/flower-planting-with-no-adjacent/

Solution

We can use greedy strategy: use dfs and each time color node to the color which are not among their neighbours.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def gardenNoAdj(self, n, paths):
        G = defaultdict(list)
        for x, y in paths:
            G[x] += [y]
            G[y] += [x]
            
        colors = [0] * (n + 1)
        def dfs(node):
            if colors[node] != 0: return
            cands = set([1, 2, 3, 4])
            for neib in G[node]:
                cands.discard(colors[neib])
                
            colors[node] = list(cands)[0]
            for neib in G[node]:
                dfs(neib)
        
        for i in range(1, n + 1):
            if colors[i] == 0: dfs(i)
        return colors[1:]