Flower Planting With No Adjacent

The problem asks us to assign flower types to each garden, ensuring that no two connected gardens have the same flower type. Since there are only four flower types and each garden has at most three paths, we can always find a solution.

Solution

Create a graph to represent the connections between the gardens.
For each garden, look at the neighboring gardens and find the flower types already assigned to them.
Assign the first flower type that hasn’t been assigned to any neighboring garden.

 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
from collections import defaultdict

class Solution:
    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]:
        # Creating a graph using defaultdict
        graph = defaultdict(list)

        # Adding paths to the graph
        for xi, yi in paths:
            graph[xi - 1].append(yi - 1)
            graph[yi - 1].append(xi - 1)

        # Result array to store the type of flower in each garden
        result = [0] * n

        # Iterate through gardens
        for garden in range(n):
            # Find the flower types in neighboring gardens
            used_types = {result[neighbor] for neighbor in graph[garden]}

            # Find the first type that is not used in neighboring gardens
            for flower_type in range(1, 5):
                if flower_type not in used_types:
                    result[garden] = flower_type
                    break

        return result

Explanation

We first build a graph to represent the connections between the gardens.
Then we iterate through each garden, look at the flower types assigned to its neighboring gardens, and choose the first type not used by its neighbors.
Since there are at most three neighbors and four flower types, we can always find a suitable type.

The time complexity of this solution is O(n), where n is the number of gardens, and the space complexity is also O(n), considering the graph storage and result array.

title: Flower Planting With No Adjacent tags: map filter graph 1-based-array-indexing adjacency-list

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. In each garden, you want to plant one of 4 types of flowers.

All gardens have at most 3 paths coming into or leaving it. Your task is to choose a flower type for each garden such that, for any two gardens connected by a path, they have different types of flowers.

Return any such a choice as an array answer, where answer[i] is the type of flower planted in the (i+1)th garden. The flower types are denoted 1, 2, 3, or 4. It is guaranteed an answer exists.

Input:

n - garden number
paths - path between two gardens

 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
# @param {Integer} n
# @param {Integer[][]} paths
# @return {Integer[]}
def garden_no_adj(n, paths)
  # Create a graph
  graph = {}
	# Create adjacency list from the edges
  paths.each do |u, v|
    graph[u] ? graph[u] << v : graph[u] = [v]
    graph[v] ? graph[v] << u : graph[v] = [u]
  end
    
  flowers = []
	# Paint the garden
  for i in (1..n) do
    if graph[i]
		  # Use a color that has not been used yet (map + filter)
      choices = [1, 2, 3, 4] - graph[i].map { |v| flowers[v - 1] }
    else
      choices = [1, 2, 3, 4]
    end
 	  # Due to 1 based indexing
    flowers[i - 1] = choices.first
  end
    
  return flowers
end

n = 3 
paths = [[1,2],[2,3],[3,1]]

p garden_no_adj(n, paths)