1042. Flower Planting With No Adjacent


Problem Description

This problem involves n gardens, each needing to be planted with one of 4 types of flowers. The gardens are connected by bidirectional paths, and each garden can have at most 3 paths connected to it. The crux of the problem is to choose the type of flower for each garden in such a way that no two gardens connected by a path have the same type of flower. The goal is to find any one configuration that satisfies this condition. The final output should be an array where the element at the i-th position refers to the type of flower in the (i+1)th garden. You're assured that there is at least one solution to this problem.

Intuition

Imagine each garden as a node in a graph and each path as an edge connecting two nodes. Since a garden can have at most 3 paths, a node can have a maximum of 3 edges. To solve this, we can iterate through each garden and choose for it the lowest numbered flower type which hasn't been used by its connected neighbors.

The intuition behind this approach is that since each garden can have at most 3 paths, there is always at least one type of flower (out of the 4 available types) that is not used by any neighbor garden. By iterating through each garden, we keep track of the types used by its neighbors and then assign the first available type.

The solution uses a graph represented as an adjacency list, where the key is the garden and the value is a list of connected gardens. As it iterates through each garden, it dynamically updates the assigned flower types and maintains a set of used flower types for the current garden's neighbors. By ensuring that no adjacent gardens share a flower type, we respect the constraint and construct a valid configuration for planting flowers.

Solution Approach

The implementation employs a graph-based approach and makes use of Python's built-in data structures:

  1. Default Dictionary for Adjacency List: The graph is represented using a defaultdict from Python's collections module, which provides a convenient way to store the adjacency list. Every garden is keyed to a list of neighbor gardens that are connected by paths.

  2. Iterating Over Gardens: We iterate sequentially over each garden. Here, the garden's index is treated as its label (decremented by 1 as indices in Python are 0-based, but gardens are labeled from 1 to n).

  3. Tracking Used Flower Types: A set is created for each garden to keep track of the flower types used by its neighboring gardens.

  4. Assigning Flower Types: For each garden, we loop over the possible flower types (1 through 4). We pick the first flower type that is not present in the set of used types and assign this flower type to the current garden.

  5. Updating the Answer: After a valid flower type is chosen for a garden, it is saved to the ans list, which initially is filled with zeroes.

  6. Returning the Solution: After all gardens have been assigned a flower type, we return the ans list, which now contains the type of flower for each garden satisfying the problem's constraints.

In more detail, for each garden x, we perform the following steps:

  • Get the set used of flower types that have already been used by the neighbors of garden x.
  • Iterate through the flower types c from 1 to 4, checking if c is not in the used set.
  • When we find such a c, we assign it to ans[x] and break the inner loop since we've found a valid flower for this garden.

This greedy algorithm ensures that since no more than 3 gardens can be adjacent to a garden, there will always be at least one type of flower from the 4 available that we can plant in every garden, thus always providing a valid solution.

💪
Level Up Your
Algo Skills

Example Walkthrough

Consider a scenario with five gardens and the following paths between them: [1,2], [2,3], [3,4], [4,5], [1,5]. This means garden 1 is connected to gardens 2 and 5, garden 2 is connected to gardens 1 and 3, and so on.

Let's apply the solution approach to this example:

  • Start with an empty adjacency list and an ans list filled with zeroes, denoting that no flowers have been planted yet.

  • Interpret the paths to fill the adjacency list, which in this case results in:

    11 -> [2, 5]
    22 -> [1, 3]
    33 -> [2, 4]
    44 -> [3, 5]
    55 -> [4, 1]
  • Begin iterating from garden 1 to 5.

  • For garden 1, check the flower types of its neighbors (gardens 2 and 5 which have not been planted yet) and note that all flower types (1, 2, 3, 4) are available. Choose the lowest number which is 1, and assign it to the garden, so ans[1] = 1.

  • Move to garden 2, which is connected to garden 1 (planted with flower type 1) and garden 3 (not yet planted). The available flower types are 2, 3, and 4. Pick the lowest, which is 2, so ans[2] = 2.

  • For garden 3, connected to garden 2 (flower type 2) and garden 4 (not yet planted). Available types are 1, 3, and 4. Choose the lowest, so ans[3] = 1.

  • Move to garden 4, which has neighbors 3 and 5. Garden 3 has flower type 1, and garden 5 is unplanted. The choices are 2, 3, or 4. Pick the lowest, so ans[4] = 2.

  • Finally, garden 5 is connected to gardens 1 and 4, which have flower types 1 and 2, respectively. The remaining flowers are 3 and 4. So we pick 3, and ans[5] = 3.

  • The flower assignments for each of the five gardens represented by the ans list are now [1, 2, 1, 2, 3].

This walkthrough demonstrates the straightforward greedy strategy described in the solution approach, reflecting how we can always ensure that each garden has a unique type of flower compared to its immediate neighbors.

Python Solution

1from collections import defaultdict
2
3class Solution:
4    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]):
5        # Build a graph where each node represents a garden and edges represent paths
6        graph = defaultdict(list)
7        for path in paths:
8            # Decrementing by 1 to convert the 1-indexed gardens to 0-indexed for easier array manipulation
9            a, b = path[0] - 1, path[1] - 1
10            graph[a].append(b)
11            graph[b].append(a)
12      
13        # Initialize the answer array where each garden's flower type will be stored
14        garden_flower_types = [0] * n
15      
16        # Loop through each garden and choose a flower type
17        for garden in range(n):
18            # Build a set of used flower types for the current garden's adjacent gardens
19            used_flower_types = {garden_flower_types[adj] for adj in graph[garden]}
20          
21            # Assign the lowest flower type (1-4) that is not used by adjacent gardens
22            for flower_type in range(1, 5):
23                if flower_type not in used_flower_types:
24                    garden_flower_types[garden] = flower_type
25                    break
26                  
27        # Return the list of assigned flower types for each garden
28        return garden_flower_types
29

Java Solution

1class Solution {
2    public int[] gardenNoAdj(int n, int[][] paths) {
3        // Create an adjacency list to represent gardens and their paths
4        List<Integer>[] graph = new List[n];
5        // Initialize each list within the graph
6        Arrays.setAll(graph, k -> new ArrayList<>());
7        // Fill the adjacency list with the paths provided
8        for (int[] path : paths) {
9            int garden1 = path[0] - 1; // Subtract 1 to convert to 0-based index
10            int garden2 = path[1] - 1; // Subtract 1 to convert to 0-based index
11            graph[garden1].add(garden2); // Add a path from garden1 to garden2
12            graph[garden2].add(garden1); // Add a path from garden2 to garden1 (undirected graph)
13        }
14
15        // Answer array to store the type of flowers in each garden
16        int[] flowerTypes = new int[n];
17        // Array to keep track of used flower types
18        boolean[] usedFlowers = new boolean[5]; // Index 0 is unused, as flower types are 1-4
19
20        // Assign flower types to each garden
21        for (int garden = 0; garden < n; ++garden) {
22            // Reset the usedFlowers array for the current garden
23            Arrays.fill(usedFlowers, false);
24            // Mark the flower types used by adjacent gardens
25            for (int adjacentGarden : graph[garden]) {
26                usedFlowers[flowerTypes[adjacentGarden]] = true;
27            }
28            // Find the lowest number flower type that hasn't been used by adjacent gardens
29            for (int type = 1; type < 5; ++type) {
30                if (!usedFlowers[type]) {
31                    flowerTypes[garden] = type; // Assign this flower type to the current garden
32                    break; // Exit loop after assigning a type
33                }
34            }
35        }
36        // Return the array containing the flower types for each garden
37        return flowerTypes;
38    }
39}
40

C++ Solution

1#include <vector>
2#include <cstring> // Include C string library for memset
3
4using namespace std; // Use the standard namespace
5
6class Solution {
7public:
8    // Method to assign garden types without adjacent gardens having the same type.
9    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
10        // Create an adjacency list for the gardens.
11        vector<vector<int>> adjList(n);
12        for (const auto& path : paths) {
13            int garden1 = path[0] - 1; // Convert to 0-based index.
14            int garden2 = path[1] - 1; // Convert to 0-based index.
15            // Add each path to the adjacency list in both directions.
16            adjList[garden1].push_back(garden2);
17            adjList[garden2].push_back(garden1);
18        }
19      
20        // Vector to store the type of flowers planted in each garden.
21        vector<int> flowerTypes(n, 0);
22        // Boolean array to keep track of used flower types for adjacency.
23        bool usedFlowerTypes[5];
24      
25        // Iterate through each garden to assign flower types.
26        for (int garden = 0; garden < n; ++garden) {
27            // Reset the used flower types.
28            memset(usedFlowerTypes, false, sizeof(usedFlowerTypes));
29          
30            // Mark the flower types already used by adjacent gardens.
31            for (int adjacentGarden : adjList[garden]) {
32                usedFlowerTypes[flowerTypes[adjacentGarden]] = true;
33            }
34          
35            // Assign the lowest flower type that isn't used.
36            for (int flowerType = 1; flowerType <= 4; ++flowerType) {
37                if (!usedFlowerTypes[flowerType]) {
38                    flowerTypes[garden] = flowerType;
39                    break; // Stop looping once a flower type is assigned.
40                }
41            }
42        }
43      
44        return flowerTypes; // Return the final assignment of flower types.
45    }
46};
47

Typescript Solution

1function gardenNoAdj(numberOfGardens: number, paths: number[][]): number[] {
2    // Create an adjacency list to store the connections between gardens
3    const graph: number[][] = new Array(numberOfGardens).fill(0).map(() => []);
4    // Build the graph from the given paths
5    for (const [garden1, garden2] of paths) {
6        graph[garden1 - 1].push(garden2 - 1);
7        graph[garden2 - 1].push(garden1 - 1);
8    }
9    // Initialize an array to hold the flower type for each garden
10    const flowerTypes: number[] = new Array(numberOfGardens).fill(0);
11    // Iterate through each garden to assign the flower types
12    for (let currentGarden = 0; currentGarden < numberOfGardens; ++currentGarden) {
13        // Track usage of flower types from 1 to 4, as each garden can have 1 of 4 different types of flowers
14        const usedFlowerTypes: boolean[] = new Array(5).fill(false);
15        // Mark the flower types used by the neighboring gardens
16        for (const adjacentGarden of graph[currentGarden]) {
17            usedFlowerTypes[flowerTypes[adjacentGarden]] = true;
18        }
19        // Assign the lowest numbered flower type that isn't used by any neighboring gardens
20        for (let flowerType = 1; flowerType < 5; ++flowerType) {
21            if (!usedFlowerTypes[flowerType]) {
22                flowerTypes[currentGarden] = flowerType;
23                break;
24            }
25        }
26    }
27    // Return the array containing the flower type for each garden
28    return flowerTypes;
29}
30

Time and Space Complexity

The code defines a Solution class with the gardenNoAdj method, which assigns a unique type of flower to each garden given the constraints that no adjacent gardens can have the same type of flower. There are n gardens numbered from 1 to n and at most 4 types of flowers.

Time Complexity:

The time complexity is determined by the following factors:

  1. Building the graph: The loop iterates through the paths array, which might contain up to n(n-1)/2 paths in the worst case (a complete graph). This process has a time complexity of O(E) where E is the number of paths (edges).

  2. Assigning flowers to gardens: There's an outer loop iterating n times for each garden and, inside it, a nested loop that iterates through the adjacent gardens (up to n-1 times in the worst-case scenario for a complete graph). However, since each garden is limited to 3 edges (paths) to prevent excessive adjacency according to the problem statement, the inner loop has a constant factor, and thus, this part has a time complexity of O(n).

  3. Choosing a flower that hasn't been used: We iterate through the 4 types of flowers. This is a constant operation since the number of flower types does not change with n.

Thus, the total time complexity is O(E + n), where E is the number of edges or paths.

Space Complexity:

The space complexity is determined by the following factors:

  1. The graph g: In the worst-case scenario (a complete graph), each node connects to n-1 other nodes. Therefore, the space required by this graph is O(E) where E is the number of edges.

  2. ans array: This is an array of size n, so it consumes O(n) space.

  3. used set: At most, the set contains 4 elements because there are only 4 different types of flowers. This is a constant space O(1).

Considering all factors, the total space complexity of the algorithm is O(E + n). The space taken by the used set is negligible in comparison to the graph and ans array.

Combining both the time and space complexities, we sum them up as O(E + n) for time complexity and O(E + n) for space complexity.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫