Scale Engineer

Flower Planting With No Adjacent

Med
#0996Time: 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: 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.1 company
Algorithms
Depth-First SearchBreadth-First Search
Data structures
Graph
Companies
Vimeo

Prompt

You have n gardens, labeled from 1 to n, and an array paths where paths[i] = [xi, yi] describes a bidirectional path between garden xi to garden yi. 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 <= 104
  • 0 <= paths.length <= 2 * 104
  • paths[i].length == 2
  • 1 <= xi, yi <= n
  • xi != yi
  • Every garden has at most 3 paths coming into or leaving it.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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:

  1. Build an adjacency list for the graph.
  2. Create a result array, answer, to store the color of each garden.
  3. Loop through each garden from i = 0 to n-1.
  4. For each garden i, check the colors of its neighbors. Keep track of the colors that are already taken by neighbors.
  5. 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

Time

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

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.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem