1042. Flower Planting With No Adjacent LeetCode Solution

Last updated: February 21, 2025

In this guide, you will get 1042. Flower Planting With No Adjacent LeetCode Solution with the best time and space complexity. The solution to Flower Planting With No Adjacent problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Flower Planting With No Adjacent solution in C++
Flower Planting With No Adjacent solution in Java
Flower Planting With No Adjacent solution in Python
Additional Resources

1042. Flower Planting With No Adjacent LeetCode Solution image

Problem Statement of Flower Planting With No Adjacent

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1042. Flower Planting With No Adjacent LeetCode Solution in C++

class Solution {
 public:
  vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
    vector<int> ans(n);  // ans[i] := 1, 2, 3, or 4
    vector<vector<int>> graph(n);

    for (const vector<int>& path : paths) {
      const int u = path[0] - 1;
      const int v = path[1] - 1;
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    for (int u = 0; u < n; ++u) {
      int used = 0;
      for (const int v : graph[u])
        used |= 1 << ans[v];
      ans[u] = getFirstUnusedType(used);
    }

    return ans;
  }

 private:
  int getFirstUnusedType(int used) {
    for (int type = 1; type <= 4; ++type)
      if ((used >> type & 1) == 0)
        return type;
    throw;
  }
};
/* code provided by PROGIEZ */

1042. Flower Planting With No Adjacent LeetCode Solution in Java

class Solution {
  public int[] gardenNoAdj(int n, int[][] paths) {
    int[] ans = new int[n]; // ans[i] := 1, 2, 3, or 4
    List<Integer>[] graph = new List[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] path : paths) {
      final int u = path[0] - 1;
      final int v = path[1] - 1;
      graph[u].add(v);
      graph[v].add(u);
    }

    for (int u = 0; u < n; ++u) {
      int used = 0;
      for (final int v : graph[u])
        used |= 1 << ans[v];
      ans[u] = getFirstUnusedType(used);
    }

    return ans;
  }

  private int getFirstUnusedType(int used) {
    for (int type = 1; type <= 4; ++type)
      if ((used >> type & 1) == 0)
        return type;
    throw new IllegalArgumentException();
  }
}
// code provided by PROGIEZ

1042. Flower Planting With No Adjacent LeetCode Solution in Python

class Solution:
  def gardenNoAdj(self, n: int, paths: list[list[int]]) -> list[int]:
    ans = [0] * n  # ans[i] := 1, 2, 3, or 4
    graph = [[] for _ in range(n)]

    for x, y in paths:
      u = x - 1
      v = y - 1
      graph[u].append(v)
      graph[v].append(u)

    for u in range(n):
      used = functools.reduce(operator.or_, (1 << ans[v] for v in graph[u]), 0)
      ans[u] = next(type_
                    for type_ in range(1, 5)
                    if not (used >> type_ & 1))

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents