# Flower Planting With No Adjacent
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/flower-planting-with-no-adjacent)
Canonical: https://scaleengineer.com/dsa/problems/flower-planting-with-no-adjacent
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Graph
**Companies:** [Vimeo](https://scaleengineer.com/companies/vimeo)
---
## Problem
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
## Backtracking
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.
**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).
**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.
### Explanation
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.

```java
import java.util.*;

class Solution {
    private List<Integer>[] adj;
    private int[] colors;
    private int n;

    public int[] gardenNoAdj(int n, int[][] paths) {
        this.n = n;
        this.adj = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int[] path : paths) {
            int u = path[0] - 1;
            int v = path[1] - 1;
            adj[u].add(v);
            adj[v].add(u);
        }

        this.colors = new int[n];
        solve(0);
        return colors;
    }

    private boolean solve(int gardenIndex) {
        if (gardenIndex == n) {
            return true;
        }

        for (int c = 1; c <= 4; c++) {
            if (isColorValid(gardenIndex, c)) {
                colors[gardenIndex] = c;
                if (solve(gardenIndex + 1)) {
                    return true;
                }
                // Backtracking by trying the next color in the loop.
                // No need to reset colors[gardenIndex] = 0 because a solution is guaranteed.
            }
        }
        return false; // Should not be reached.
    }

    private boolean isColorValid(int gardenIndex, int color) {
        for (int neighbor : adj[gardenIndex]) {
            if (colors[neighbor] == color) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- 1. Build an adjacency list to represent the garden connections.
- 2. Create a `colors` array of size `n` to store the flower type for each garden, initialized to 0 (uncolored).
- 3. Define a recursive function `solve(gardenIndex)` that attempts to color gardens from `gardenIndex` to `n-1`.
- 4. **Base Case:** If `gardenIndex` equals `n`, all gardens are colored, so a solution has been found. Return `true`.
- 5. **Recursive Step:** For the current `gardenIndex`, iterate through the four flower types (1 to 4).
- 6. For each color, check if it's valid. A color is valid if none of the adjacent gardens have this color.
- 7. If the color is valid, assign it to `colors[gardenIndex]` and make a recursive call `solve(gardenIndex + 1)`.
- 8. If the recursive call returns `true`, it means a solution is found down the line, so propagate `true` up the call stack.
- 9. 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.
- 10. If all four colors are tried and none lead to a solution, return `false` (this case won't be reached in this specific problem).
- 11. Start the process by calling `solve(0)`.

## 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.
**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.
**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).
### Explanation
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`.

```java
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;
    }
}
```
### 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.
- 2. Create an `answer` array of size `n` to store the chosen flower type for each garden, initialized with 0s.
- 3. Iterate through each garden `i` from 0 to `n-1`.
- 4. For each garden `i`, determine the colors used by its neighbors. A boolean array `usedColors` of size 5 can be used for this.
- 5. 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`).
- 6. Iterate through the four possible flower types (1, 2, 3, 4).
- 7. Assign the first flower type `c` that is not used (i.e., `!usedColors[c]`) to the current garden `i` by setting `answer[i] = c`.
- 8. Break the inner loop once a color is assigned, as we only need one valid color, and move to the next garden.
- 9. After the main loop finishes, the `answer` array will contain a valid coloring. Return it.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> gardenNoAdj(int n, vector<vector<int>> &paths) {
    vector<vector<int>> g(n);
    for (auto &p : paths) {
      int x = p[0] - 1, y = p[1] - 1;
      g[x].push_back(y);
      g[y].push_back(x);
    }
    vector<int> ans(n);
    bool used[5];
    for (int x = 0; x < n; ++x) {
      memset(used, false, sizeof(used));
      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;
  }
};

```

### Python

```python
class Solution:
    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

```