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 Search Breadth-First Search

Data structures

Graph

Companies

Vimeo

Prompt

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

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:

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.

1import java.util.*;2 3class Solution {4    public int[] gardenNoAdj(int n, int[][] paths) {5        // Adjacency list to represent the graph6        List<Integer>[] adj = new ArrayList[n];7        for (int i = 0; i < n; i++) {8            adj[i] = new ArrayList<>();9        }10        for (int[] path : paths) {11            // Gardens are 1-indexed, arrays are 0-indexed12            int u = path[0] - 1;13            int v = path[1] - 1;14            adj[u].add(v);15            adj[v].add(u);16        }17 18        // answer[i] will store the color of garden i (0-indexed)19        int[] answer = new int[n];20 21        // Iterate through each garden22        for (int i = 0; i < n; i++) {23            // Use a boolean array to track used colors by neighbors24            boolean[] usedColors = new boolean[5]; // For colors 1, 2, 3, 425 26            // Check colors of adjacent gardens that are already colored27            for (int neighbor : adj[i]) {28                if (answer[neighbor] != 0) { // If neighbor is already colored29                    usedColors[answer[neighbor]] = true;30                }31            }32 33            // Find the first unused color34            for (int c = 1; c <= 4; c++) {35                if (!usedColors[c]) {36                    answer[i] = c;37                    break; // Found a color, move to the next garden38                }39            }40        }41        return answer;42    }43}

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

This approach uses a standard backtracking algorithm to solve the graph coloring problem. It tries to assign a color to each garden one by one, and if an assignment leads to a conflict with its neighbors, it backtracks and tries a different color. This is a general but often inefficient method for such problems.

Algorithm

1. Build an adjacency list to represent the garden connections.
1. Create a colors array of size n to store the flower type for each garden, initialized to 0 (uncolored).
1. Define a recursive function solve(gardenIndex) that attempts to color gardens from gardenIndex to n-1.
1. Base Case: If gardenIndex equals n, all gardens are colored, so a solution has been found. Return true.
1. Recursive Step: For the current gardenIndex, iterate through the four flower types (1 to 4).
1. For each color, check if it's valid. A color is valid if none of the adjacent gardens have this color.
1. If the color is valid, assign it to colors[gardenIndex] and make a recursive call solve(gardenIndex + 1).
1. If the recursive call returns true, it means a solution is found down the line, so propagate true up the call stack.
1. If the recursive call returns false, it means this choice of color did not lead to a solution. Backtrack by trying the next color. In a general problem, you might reset the color, but since a solution is guaranteed here, the first valid path will succeed.
1. If all four colors are tried and none lead to a solution, return false (this case won't be reached in this specific problem).
1. Start the process by calling solve(0).

Walkthrough

The problem can be modeled as a graph where gardens are vertices and paths are edges. We need to color the vertices. Backtracking explores the search space of all possible color assignments recursively.

We define a function, say solve(gardenIndex), which tries to color the garden at gardenIndex. It iterates through the four possible colors. For each color, it checks if assigning it to the current garden would violate the condition (i.e., if any neighbor already has that color). If the color is valid, it's assigned, and the function recursively calls itself for the next garden, solve(gardenIndex + 1). If the recursive call eventually finds a complete, valid coloring, it returns true. If it fails, we backtrack and try the next color for the current garden. Since the problem guarantees a solution exists, this process will eventually find one.

1import java.util.*;2 3class Solution {4    private List<Integer>[] adj;5    private int[] colors;6    private int n;7 8    public int[] gardenNoAdj(int n, int[][] paths) {9        this.n = n;10        this.adj = new ArrayList[n];11        for (int i = 0; i < n; i++) {12            adj[i] = new ArrayList<>();13        }14        for (int[] path : paths) {15            int u = path[0] - 1;16            int v = path[1] - 1;17            adj[u].add(v);18            adj[v].add(u);19        }20 21        this.colors = new int[n];22        solve(0);23        return colors;24    }25 26    private boolean solve(int gardenIndex) {27        if (gardenIndex == n) {28            return true;29        }30 31        for (int c = 1; c <= 4; c++) {32            if (isColorValid(gardenIndex, c)) {33                colors[gardenIndex] = c;34                if (solve(gardenIndex + 1)) {35                    return true;36                }37                // Backtracking by trying the next color in the loop.38                // No need to reset colors[gardenIndex] = 0 because a solution is guaranteed.39            }40        }41        return false; // Should not be reached.42    }43 44    private boolean isColorValid(int gardenIndex, int color) {45        for (int neighbor : adj[gardenIndex]) {46            if (colors[neighbor] == color) {47                return false;48            }49        }50        return true;51    }52}

Complexity

Time

O(4^n * n) in the worst case for a general graph. The branching factor is 4, and the depth of recursion is n. The check for color validity takes O(degree), which is at most n. While the low degree constraint prunes the search space significantly, the exponential nature makes it too slow for the given constraints.

Space

O(n + E) for the adjacency list and O(n) for the recursion stack, where E is the number of paths. This simplifies to O(n + E).

Trade-offs

Pros

It's a general method for solving constraint satisfaction problems like graph coloring.
Guaranteed to find a solution if one exists.

Cons

Extremely inefficient for the given constraints (n up to 10^4).
Will likely result in a Time Limit Exceeded (TLE) verdict on most platforms.
Overkill for a problem with a guaranteed simple solution structure.

Solutions

Solution

1class Solution {2public3  int[] gardenNoAdj(int n, int[][] paths) {4    List<Integer>[] g = new List[n];5    Arrays.setAll(g, k->new ArrayList<>());6    for (var p : paths) {7      int x = p[0] - 1, y = p[1] - 1;8      g[x].add(y);9      g[y].add(x);10    }11    int[] ans = new int[n];12    boolean[] used = new boolean[5];13    for (int x = 0; x < n; ++x) {14      Arrays.fill(used, false);15      for (int y : g[x]) {16        used[ans[y]] = true;17      }18      for (int c = 1; c < 5; ++c) {19        if (!used[c]) {20          ans[x] = c;21          break;22        }23      }24    }25    return ans;26  }27}

1class Solution {2public:3  vector<int> gardenNoAdj(int n, vector<vector<int>> &paths) {4    vector<vector<int>> g(n);5    for (auto &p : paths) {6      int x = p[0] - 1, y = p[1] - 1;7      g[x].push_back(y);8      g[y].push_back(x);9    }10    vector<int> ans(n);11    bool used[5];12    for (int x = 0; x < n; ++x) {13      memset(used, false, sizeof(used));14      for (int y : g[x]) {15        used[ans[y]] = true;16      }17      for (int c = 1; c < 5; ++c) {18        if (!used[c]) {19          ans[x] = c;20          break;21        }22      }23    }24    return ans;25  }26};

1class Solution:2    def gardenNoAdj(self, n: int, paths: List[List[int]]) -> List[int]: g = defaultdict(list) for x, y in paths: x, y = x - 1, y - 1 g[x]. append(y) g[y]. append(x) ans = [0] * n for x in range(n): used = {ans[y] for y in g[x]} for c in range(1, 5): if c not in used: 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 problem