Flower Planting With No Adjacent - Leetcode Solution

The Flower Planting with No Adjacent problem on LeetCode can be solved by using a graph-based approach. The problem statement is as follows:

Suppose you have N gardens, labeled 1 to N. In each garden, you want to plant one of 4 types of flowers.

• There is a constraint that you can not plant the same type of flower in adjacent gardens.

• You are provided a list of paths, where paths[i] = [x, y] represents a bidirectional pathway between garden x and garden y.

• You must plant the flowers such that each garden has exactly one type of flower.

• Return any such a possible way of arranging the flowers such that no two adjacent gardens have the same type of flower. If it is impossible, return an empty array.

The detailed solution to the problem is as follows:

Step 1: Create an adjacency list for the given list of paths. This will help us to easily traverse the gardens and their respective neighbors.

Step 2: Create an array to store the color of each garden. Initially, set all garden colors to 0.

Step 3: Iterate through each garden in the garden list and assign a color to it based on the following conditions:

• If a garden has not been assigned a color, assign it any color (1, 2, 3, or 4).

• If a garden has already been assigned a color, skip it.

• If any adjacent garden has the same color, then the current garden can not be painted with that color. So, assign the next available color to the garden (i.e., if the garden is initially colored with 1 and its neighbor has also been colored with 1, change the color of the current garden to 2).

Step 4: Return the array of garden colors.

The time complexity of this algorithm is O(N+P), where N is the number of gardens, and P is the number of paths. The space complexity of this algorithm is O(N), where N is the number of gardens.

Here's the implementation of the above algorithm in Python:

from collections import defaultdict

class Solution:
    def gardenNoAdj(self, N: int, paths: List[List[int]]) -> List[int]:
        # Step 1: Create an adjacency list
        adj_list = defaultdict(list)
        for src, dest in paths:
            adj_list[src].append(dest)
            adj_list[dest].append(src)
            
        # Step 2: Create an array to store the garden colors
        colors = [0] * N
        
        # Step 3: Assign colors to the gardens
        for i in range(1, N+1):
            if colors[i-1] == 0:
                colors[i-1] = 1
            
            for neighbor in adj_list[i]:
                if colors[neighbor-1] != 0 and colors[i-1] == colors[neighbor-1]:
                    colors[i-1] += 1
            
            if colors[i-1] > 4:
                colors[i-1] = 1
                
        # Step 4: Return the array of garden colors     
        return colors

As mentioned earlier, there can be multiple possible solutions to this problem as long as the conditions mentioned in the problem statement are satisfied.

1