Solution to Leetcode problem 1042: Flower Planting With No Adjacent

In this Leetcode problem, we are asked to assign a type of flower (1, 2, 3, or 4) to each garden (1..N). We are given a paths list signaling pairs of gardens that are neighbors. A garden can’t have more than 3 neighbors. We should assign the types of flower for each garden so that 2 garden that are neighbors don’t have the same type of flowers.

Problem statement

This problem almost obviously set up a graph, in which we need to assign a label to each node. It is a coloring problem then. Since there will be no more than 3 neighbors for each node, no matter how you traverse or assign colors, there will always be a free one to grab once you color all the neighbors.

Therefore, pick the order of the nodes and traverse it your favorite way. I decided to go through the nodes in order, garden 1 to garden N. Also note that because the colors and the gardens are not 0-indexed, the code plays with indices a bit more than I would like.

First define the GraphNode:

// Define Graph struct
type GraphNode struct {
  Label int
  Neighbors []*GraphNode
}

Label isn’t that useful given the way I used the graph, but it represents the index of the represented garden, from 1 to N.