Code Implementation

class Solution:
    def gardenNoAdj(self, n, paths):
        from collections import defaultdict
        graph = defaultdict(list)
        for u, v in paths:
            graph[u-1].append(v-1)
            graph[v-1].append(u-1)
        res = [0] * n
        for i in range(n):
            used = set()
            for nei in graph[i]:
                if res[nei]:
                    used.add(res[nei])
            for color in range(1, 5):
                if color not in used:
                    res[i] = color
                    break
        return res
      

class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>> graph(n);
        for (auto& p : paths) {
            graph[p[0]-1].push_back(p[1]-1);
            graph[p[1]-1].push_back(p[0]-1);
        }
        vector<int> res(n, 0);
        for (int i = 0; i < n; ++i) {
            vector<bool> used(5, false);
            for (int nei : graph[i]) {
                if (res[nei])
                    used[res[nei]] = true;
            }
            for (int color = 1; color <= 4; ++color) {
                if (!used[color]) {
                    res[i] = color;
                    break;
                }
            }
        }
        return res;
    }
};
      

class Solution {
    public int[] gardenNoAdj(int n, int[][] paths) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            graph.add(new ArrayList<>());
        for (int[] p : paths) {
            graph.get(p[0]-1).add(p[1]-1);
            graph.get(p[1]-1).add(p[0]-1);
        }
        int[] res = new int[n];
        for (int i = 0; i < n; ++i) {
            boolean[] used = new boolean[5];
            for (int nei : graph.get(i)) {
                if (res[nei] != 0)
                    used[res[nei]] = true;
            }
            for (int color = 1; color <= 4; ++color) {
                if (!used[color]) {
                    res[i] = color;
                    break;
                }
            }
        }
        return res;
    }
}
      

var gardenNoAdj = function(n, paths) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of paths) {
        graph[u-1].push(v-1);
        graph[v-1].push(u-1);
    }
    const res = Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        const used = new Set();
        for (const nei of graph[i]) {
            if (res[nei]) used.add(res[nei]);
        }
        for (let color = 1; color <= 4; ++color) {
            if (!used.has(color)) {
                res[i] = color;
                break;
            }
        }
    }
    return res;
};
      

Problem Description

You are given n gardens, numbered from 1 to n. Some gardens are connected by bidirectional paths, given as a list paths where each element is a pair [x, y] indicating a path between garden x and garden y.

Each garden must be planted with one type of flower. There are exactly four types of flowers, labeled 1, 2, 3, and 4. No two gardens that are directly connected by a path may have the same type of flower.

Return any valid assignment of flowers to gardens such that the rule above is satisfied. There is guaranteed to be at least one valid solution for all inputs.

Key constraints:

• Each garden must be assigned exactly one flower type.
• No two adjacent gardens (connected by a path) can have the same flower type.
• There are only four flower types to use, but each can be used multiple times (just not for adjacent gardens).
• There may be multiple valid answers; return any one.

Thought Process

The problem can be seen as a type of graph coloring problem, where each garden is a node and each path is an edge. The main challenge is to assign a color (flower type) to each node so that no two connected nodes share the same color.

A brute-force approach would be to try all possible assignments of flower types to gardens and check if the constraints are met. However, this quickly becomes infeasible as the number of gardens increases, since the number of combinations grows exponentially.

But, the problem guarantees that each garden has at most three connections (since there are only four flower types, and a node with four or more neighbors would make it impossible). This allows us to use a greedy strategy: for each garden, we can always find at least one flower type not used by its neighbors.

The key insight is that with four flower types and at most three neighbors per garden, we can always pick a flower type for any garden that is different from its adjacent gardens.

Solution Approach

The solution proceeds as follows:

1. Build the Graph:
   • Create an adjacency list to represent connections between gardens. Each garden's list contains the indices of gardens it is connected to.
2. Assign Flower Types Greedily:
   • Initialize a result array res of length n with all zeros (meaning unassigned).
   • For each garden (from 0 to n-1):
     • Check which flower types have already been assigned to its neighbors.
     • Pick the first flower type (from 1 to 4) not used by its neighbors and assign it to the current garden.
3. Return the Result:
   • After all gardens are assigned, return the result array.

This approach works efficiently because the constraints guarantee that at each step, at least one flower type is available.

Example Walkthrough

Let's walk through an example:

Input: n = 4, paths = [[1,2],[3,4]]

• There are 4 gardens. Garden 1 is connected to 2, and 3 is connected to 4.
• Adjacency list:
  • Garden 1: [2]
  • Garden 2: [1]
  • Garden 3: [4]
  • Garden 4: [3]
• Start with res = [0, 0, 0, 0].
• Assign flowers:
  1. Garden 1: neighbors = [2] (unassigned), so assign flower 1. res = [1, 0, 0, 0]
  2. Garden 2: neighbor 1 has flower 1, so pick flower 2. res = [1, 2, 0, 0]
  3. Garden 3: neighbor 4 unassigned, so assign flower 1. res = [1, 2, 1, 0]
  4. Garden 4: neighbor 3 has flower 1, so pick flower 2. res = [1, 2, 1, 2]
• Output: [1, 2, 1, 2] (or any valid assignment).

At each step, we never run out of flower types to assign, thanks to the constraints.

Time and Space Complexity

Brute-force approach:

• Would try all 4^n possible assignments, which is exponential and not feasible for large n.

• Time Complexity: O(n + m), where n is the number of gardens and m is the number of paths. Building the adjacency list takes O(m), and assigning flowers to each garden is O(1) per garden (since each has at most 3 neighbors), so total is linear.
• Space Complexity: O(n + m) for the adjacency list and result array.

Summary

This problem is a special case of graph coloring, made easy by the guarantee that each garden has at most three connections and there are four flower types. By greedily assigning to each garden a flower type not used by its neighbors, we ensure a valid assignment efficiently. The elegance of the solution lies in leveraging the problem's constraints to avoid complex backtracking or brute-force, resulting in a simple and fast algorithm.