We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Flower Planting With No Adjacent

Number: 1120

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given n gardens and a list of bidirectional paths connecting them, assign one of four flower types (1, 2, 3, or 4) to each garden such that no two connected gardens have the same flower type. Each garden has at most three paths connecting it to other gardens. An answer is guaranteed to exist.

Key Insights

  • The problem can be modeled as a graph coloring problem where each garden is a node.
  • Since every garden can have at most 3 adjacent gardens and we have 4 flower types, there will always be at least one available flower type for each garden.
  • A greedy approach (iterating through each garden and choosing a flower type that is not used by its neighbors) is sufficient.
  • The graph is undirected, so each edge connects two nodes, and the validity check must be performed in both directions.

Space and Time Complexity

Time Complexity: O(n + m) where n is the number of gardens and m is the number of paths. Space Complexity: O(n + m) for storing the adjacency list and the result array.

Solution

The solution involves constructing an adjacency list from the paths to represent the graph. Then, iterate through each garden from 1 to n and for each garden, check the flower types already assigned to its neighboring gardens. Choose the smallest flower type from the set {1, 2, 3, 4} that is not used by its neighbors and assign it. This greedy algorithm works because each garden has at most 3 neighbors, ensuring that at least one type remains available.

Code Solutions

# Function to solve the flower planting problem
def gardenNoAdj(n, paths):
    # Build the adjacency list for each garden
    garden_adj = [[] for _ in range(n)]
    for x, y in paths:
        # Convert 1-indexed garden labels to 0-indexed list indices
        garden_adj[x - 1].append(y - 1)
        garden_adj[y - 1].append(x - 1)
    
    # Array to hold the assigned flower type for each garden
    result = [0] * n
    
    # Iterate through each garden
    for garden in range(n):
        # Set to hold flower types used by neighboring gardens
        used_flowers = set()
        for neighbor in garden_adj[garden]:
            if result[neighbor] != 0:
                used_flowers.add(result[neighbor])
        
        # Choose the smallest flower type that is not used by the neighbors
        for flower in range(1, 5):
            if flower not in used_flowers:
                result[garden] = flower
                break
    return result

# Example usage:
# n = 3, paths = [[1,2],[2,3],[3,1]] results in a valid answer, e.g., [1,2,3]
print(gardenNoAdj(3, [[1,2],[2,3],[3,1]]))
← Back to All Questions