Flower planting with no adjacent

Depth-First Search Breadth-First Search Graph Theory

53.4% acceptance

Feb 25, 2026

1568

726

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn garden_no_adj(n: i32, paths: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for p in &paths {
      let (u, v) = (p[0] as usize - 1, p[1] as usize - 1);
      adj[u].push(v);
      adj[v].push(u);
    }
    let mut ans = vec![0i32; n];
    for i in 0..n {
      let used: std::collections::HashSet<i32> = adj[i].iter().map(|&j| ans[j]).collect();
      ans[i] = (1..=4).find(|c| !used.contains(c)).unwrap();
    }
    ans
  }
}