1042. Flower Planting With No Adjacent - cocoder39/coco39_LC GitHub Wiki

1042. Flower Planting With No Adjacent

All gardens have at most 3 paths coming into or leaving it.

This condition indicates that there always exists a valid option for a garden since it has at most 3 neighbours while there are 4 colors. Without this hint, will need to backtrack all options to find the valid one

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        graph = {i: [] for i in range(n+1)}
        for x, y in paths:
            graph[x].append(y)
            graph[y].append(x)
        
        color = {}
        for cur_node, neighbors in graph.items():
            if cur_node not in color:
                candidates = [True] * 5
                for neighbor in neighbors:
                    if neighbor in color:
                        candidates[color[neighbor]] = False
                for i in range(1, 5):
                    if candidates[i]:
                        color[cur_node] = i
        
        res = []
        for i in range(n):
            res.append(color[i+1])
        return res