Flower Planting With No Adjacent

#523 Most AskedMedium

Flower Planting With No Adjacent #523 Most Asked

Medium

7 views

Topics:

ArraysGraphsGreedy Algorithms

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [x_i, y_i] describes a bidirectional path between garden x_i to garden y_i. 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.

Example 1:

Input: n = 3, paths = [[1,2],[2,3],[3,1]]
Output: [1,2,3]
Explanation:
Gardens 1 and 2 have different types.
Gardens 2 and 3 have different types.
Gardens 3 and 1 have different types.
Hence, [1,2,3] is a valid answer. Other valid answers include [1,2,4], [1,4,2], and [3,2,1].

Example 2:

Input: n = 4, paths = [[1,2],[3,4]]
Output: [1,2,1,2]

Example 3:

Input: n = 4, paths = [[1,2],[2,3],[3,4],[4,1],[1,3],[2,4]]
Output: [1,2,3,4]

Constraints:

1 <= n <= 10⁴
0 <= paths.length <= 2 * 10⁴
paths[i].length == 2
1 <= x_i, y_i <= n
x_i != y_i
Every garden has at most 3 paths coming into or leaving it.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for `n` (the number of gardens)?
Are the paths in the `paths` array bidirectional, meaning if path [x, y] exists, can I plant different flowers in garden x and garden y?
If there's no possible valid flower planting, what should I return? Should I throw an error or return a specific array, such as an empty array or an array filled with a default value?
Can the input graph (represented by `n` and `paths`) be disconnected? If so, are there any specific constraints or assumptions I should make?
Are the garden numbers in the `paths` array 1-indexed or 0-indexed?

Brute Force Solution

Approach

The brute force approach to planting flowers assigns a color to each garden one at a time. For each garden, it will try every possible flower color. It then checks if the colored garden is valid by checking neighbors.

Here's how the algorithm would work step-by-step:

Start with the first garden.
Try planting a flower of color 1 in the first garden.
Then, try color 2, then color 3, and then color 4. For each of these colors:
Proceed to the next garden.
Again, try planting a flower of color 1, 2, 3 and then 4 in that garden.
After assigning a color to each garden, check if there are any adjacent gardens with the same flower color.
If there are, discard this arrangement and try a different combination of flower colors.
If there are no adjacent gardens with the same color, keep this arrangement as a valid solution.
Repeat this process for all possible color assignments.
Finally, pick any of the valid solutions (if any exist).

Code Implementation

def flower_planting_with_no_adjacent(number_of_gardens, paths):
    garden_colors = [0] * number_of_gardens

    def is_valid_arrangement():
        for garden_index in range(number_of_gardens):
            for neighbor_pair in paths:
                if neighbor_pair[0] - 1 == garden_index:
                    neighbor_index = neighbor_pair[1] - 1
                    if garden_colors[garden_index] == garden_colors[neighbor_index]:
                        return False
                elif neighbor_pair[1] - 1 == garden_index:
                    neighbor_index = neighbor_pair[0] - 1
                    if garden_colors[garden_index] == garden_colors[neighbor_index]:
                        return False
        return True

    def solve(garden_index):
        # Base case: all gardens are colored.
        if garden_index == number_of_gardens:
            if is_valid_arrangement():
                return True
            else:
                return False

        for color in range(1, 5):
            # Try assigning each color to the current garden.
            garden_colors[garden_index] = color

            # Recursively try to color the remaining gardens.
            if solve(garden_index + 1):
                return True

            # Backtrack: reset the color of the current garden.
            garden_colors[garden_index] = 0

        return False

    if solve(0):
        return garden_colors
    else:
        return []

Big(O) Analysis

Time Complexity

O(4^n) – The brute force approach explores every possible flower color assignment. For 'n' gardens, each can be colored with one of 4 colors. This results in 4 options for the first garden, 4 for the second, and so on, leading to 4*4*...*4 (n times) possible combinations. Checking the validity of each arrangement involves iterating through the adjacent gardens to determine if they have the same color as the current garden. The total number of operations then grows exponentially with the number of gardens, resulting in O(4^n) time complexity.

Space Complexity

O(N) – The brute force approach explores all possible color assignments to N gardens, where N is the number of gardens. The recursive calls to explore different color combinations create a call stack. In the worst-case scenario, where no valid solution is found until all combinations are tried, the maximum depth of the recursion is N, representing the N gardens. Therefore, the space complexity is dominated by the recursion depth, which requires O(N) space to store the stack frames. The algorithm also implicitly stores the current flower color arrangement for each garden, contributing O(N) to the space.

Optimal Solution

Approach

The goal is to assign different flower types to gardens such that no two adjacent gardens have the same flower. We use a greedy approach: for each garden, pick the smallest flower type that hasn't been used by its neighbors.

Here's how the algorithm would work step-by-step:

For each garden, determine which gardens are its direct neighbors.
For each garden, check which flower types have already been planted in its neighboring gardens.
Choose the smallest numbered flower type (1, 2, 3, or 4) that hasn't been used by any of its neighbors.
Plant this flower in the current garden.
Repeat this process for all gardens, ensuring each garden receives a suitable flower type.

Code Implementation

def flower_planting_with_no_adjacent(number_of_gardens, paths):
    garden_flowers = [0] * number_of_gardens
    adjacency_list = [[] for _ in range(number_of_gardens)]

    for path_start, path_end in paths:
        adjacency_list[path_start - 1].append(path_end - 1)
        adjacency_list[path_end - 1].append(path_start - 1)

    for garden_index in range(number_of_gardens):
        # Keep track of used flowers to avoid conflicts.
        used_flowers = set()
        for neighbor_index in adjacency_list[garden_index]:
            if garden_flowers[neighbor_index] != 0:
                used_flowers.add(garden_flowers[neighbor_index])

        # Assign the smallest available flower to current garden.
        for flower_type in range(1, 5):
            if flower_type not in used_flowers:
                garden_flowers[garden_index] = flower_type
                break

    return garden_flowers

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each of the n gardens. For each garden, it checks its neighbors to find available flower types. Since each garden has at most 3 neighbors (as stated in the problem constraints), the neighbor check takes constant time O(1). Therefore, the overall time complexity is driven by the iteration through the n gardens, resulting in O(n).

Space Complexity

O(N + E) – The algorithm requires a data structure to represent the garden's neighbors, which can be stored as an adjacency list or matrix. In the worst case, where every garden is connected to every other garden, the space used to represent these connections can be O(E), where E is the number of edges. Additionally, we use an array of size N (where N is the number of gardens) to store the assigned flower type for each garden. Therefore the space complexity is O(N + E).

Edge Cases

Case	How to Handle
Null or empty input (N = 0 gardens)	Return an empty list, as there are no gardens to plant.
Single garden (N = 1)	Return a list containing [1], as any flower color is valid.
Graph with a disconnected component	The solution should iterate through all nodes and assign a color to each disconnected component independently.
Graph with cycles	The color assignment algorithm must handle cycles without getting stuck or causing infinite recursion by maintaining visited node states.
Maximum number of gardens and connections	Ensure the solution has acceptable time and space complexity for the maximum constraint (e.g., N=10000). Use adjacency list.
A garden is connected to itself	The algorithm should ignore self-loops because you don't want to plant the same color flower in the same garden.
A garden is connected to all other gardens	The algorithm should still be able to find a valid coloring using the remaining colors.
Input contains duplicate edges in paths array.	The solution should handle this gracefully, such as using a set to keep track of already processed edges to avoid redundant operations or incorrect neighbor information.

Null or empty input (N = 0 gardens)

How to Handle:

Return an empty list, as there are no gardens to plant.

Single garden (N = 1)

How to Handle:

Return a list containing [1], as any flower color is valid.

Graph with a disconnected component

How to Handle:

The solution should iterate through all nodes and assign a color to each disconnected component independently.

Graph with cycles

How to Handle:

The color assignment algorithm must handle cycles without getting stuck or causing infinite recursion by maintaining visited node states.

Maximum number of gardens and connections

How to Handle:

Ensure the solution has acceptable time and space complexity for the maximum constraint (e.g., N=10000). Use adjacency list.

A garden is connected to itself

How to Handle:

The algorithm should ignore self-loops because you don't want to plant the same color flower in the same garden.

A garden is connected to all other gardens

How to Handle:

The algorithm should still be able to find a valid coloring using the remaining colors.

Input contains duplicate edges in paths array.

How to Handle:

The solution should handle this gracefully, such as using a set to keep track of already processed edges to avoid redundant operations or incorrect neighbor information.