Flower Planting With No Adjacent

MEDIUM

Description

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.

Approaches

Checkout 2 different approaches to solve Flower Planting With No Adjacent. Click on different approaches to view the approach and algorithm in detail.

Greedy Coloring

This approach leverages the key constraint that each garden has at most 3 neighbors. It iterates through the gardens one by one and greedily assigns the first available flower type that doesn't conflict with its already-colored neighbors. Since there are 4 available flower types and at most 3 neighbors, there will always be at least one valid choice available for any garden.

Algorithm

1. Build an adjacency list representation of the graph from the paths array. Since gardens are 1-indexed, convert them to 0-indexed for array access.
1. Create an answer array of size n to store the chosen flower type for each garden, initialized with 0s.
1. Iterate through each garden i from 0 to n-1.
1. For each garden i, determine the colors used by its neighbors. A boolean array usedColors of size 5 can be used for this.
1. Iterate through the neighbors of garden i. If a neighbor j has already been colored (i.e., answer[j] != 0), mark its color as used (e.g., usedColors[answer[j]] = true).
1. Iterate through the four possible flower types (1, 2, 3, 4).
1. Assign the first flower type c that is not used (i.e., !usedColors[c]) to the current garden i by setting answer[i] = c.
1. Break the inner loop once a color is assigned, as we only need one valid color, and move to the next garden.
1. After the main loop finishes, the answer array will contain a valid coloring. Return it.

The problem guarantees that every garden has at most 3 neighbors. We are given 4 types of flowers (colors). This setup is a direct application of a greedy coloring algorithm. For any garden, its neighbors can occupy at most 3 distinct colors. This leaves at least one color (4 - 3 = 1) available for the current garden.

Therefore, we can simply iterate through the gardens in any order (e.g., from 1 to n) and, for each garden, pick the first color that is not being used by any of its already-colored neighbors. This process is guaranteed to succeed.

The algorithm is as follows:

Build an adjacency list for the graph.
Create a result array, answer, to store the color of each garden.
Loop through each garden from i = 0 to n-1.
For each garden i, check the colors of its neighbors. Keep track of the colors that are already taken by neighbors.
Choose the smallest-numbered color (from 1 to 4) that is not taken and assign it to garden i.

import java.util.*;

class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        // Adjacency list to represent the graph
        List<Integer>[] adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] path : paths) {
            // Gardens are 1-indexed, arrays are 0-indexed
            int u = path[0] - 1;
            int v = path[1] - 1;
            adj[u].add(v);
            adj[v].add(u);
        }

        // answer[i] will store the color of garden i (0-indexed)
        int[] answer = new int[n];

        // Iterate through each garden
        for (int i = 0; i < n; i++) {
            // Use a boolean array to track used colors by neighbors
            boolean[] usedColors = new boolean[5]; // For colors 1, 2, 3, 4

            // Check colors of adjacent gardens that are already colored
            for (int neighbor : adj[i]) {
                if (answer[neighbor] != 0) { // If neighbor is already colored
                    usedColors[answer[neighbor]] = true;
                }
            }

            // Find the first unused color
            for (int c = 1; c <= 4; c++) {
                if (!usedColors[c]) {
                    answer[i] = c;
                    break; // Found a color, move to the next garden
                }
            }
        }
        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n + E), where n is the number of gardens and E is the number of paths. Building the adjacency list takes O(n + E). The main loop runs n times. Inside the loop, we iterate over a maximum of 3 neighbors and then a maximum of 4 colors, which is constant time work for each garden. Thus, the total time complexity is O(n + E).Space Complexity: O(n + E) to store the adjacency list, where n is the number of gardens and E is the number of paths. The `answer` array and `usedColors` array take O(n) and O(1) space respectively. The total space is dominated by the adjacency list.

Pros and Cons

Pros:

Very efficient and provides an optimal solution for this problem.
Simple to understand and implement.
Guaranteed to find a valid solution due to the problem's specific constraints.

Cons:

This greedy strategy is not a general solution for all graph coloring problems. It works here only because of the specific problem constraints (max degree of 3 and 4 available colors).

Code Solutions

Checking out 3 solutions in different languages for Flower Planting With No Adjacent. Click on different languages to view the code.

class Solution {
public
  int[] gardenNoAdj(int n, int[][] paths) {
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    for (var p : paths) {
      int x = p[0] - 1, y = p[1] - 1;
      g[x].add(y);
      g[y].add(x);
    }
    int[] ans = new int[n];
    boolean[] used = new boolean[5];
    for (int x = 0; x < n; ++x) {
      Arrays.fill(used, false);
      for (int y : g[x]) {
        used[ans[y]] = true;
      }
      for (int c = 1; c < 5; ++c) {
        if (!used[c]) {
          ans[x] = c;
          break;
        }
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Flower Planting With No Adjacent

Algorithms:

Depth-First SearchBreadth-First Search

Data Structures:

Graph

Companies:

Vimeo |