Flower Planting With No Adjacent solution and explanation
9 more videos on this problem
Leetcode 1042. Flower Planting With No AdjacentFraz · 10:06 · 9K views
1042. Flower Planting With No Adjacent | LEETCODE MEDIUM | GRAPH | BFScode Explainer · 11:17 · 2K views
Flower Planting With No Adjacent | Leetcode 1042 | BFS | GraphsNavyaa Sharma · 19:04 · 1K views
leetCode 1042 - Flower Planting With No Adjacent | JSer - algorithm & JavaScriptJSer · 49:54 · 1K views
1042. Flower Planting With No Adjacent (Leetcode Medium)Programming Live with Larry · 8:55 · 1K views
🌹Rose Day Special Leetcode Question | 1042 Flower Planting With No Adjacent,Google Linkedin FacebookThink Like A Coder | Newton school · 6:48 · 1K views
Vol80 - Leetcode - Problem 1042 - Flower planting with no adjacent - Golang - Phỏng vấn - Thuật toánYuh lập trình viên · 19:43 · 906 views
LeetCode 1042. Flower Planting With No Adjacent Solution Explained - JavaAlgorithms and Data Structures Course · 12:02 · 808 views
猩猩的乐园 Leetcode 1042 Flower Planting With No Adjacent猩猩的乐园 · 9:02 · 663 views
Leetcode:1042 Flower Planting With No AdjacentVikash Kumar · 38:51 · 431 views
The 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 <= 1040 <= paths.length <= 2 * 104paths[i].length == 21 <= xi, yi <= nxi != yi- Every garden has at most 3 paths coming into or leaving it.
Approach overview
Problem Overview: You have n gardens connected by bidirectional paths. Each garden must be assigned one of four flower types so that no connected gardens share the same type. The task is to return a valid assignment for all gardens.
Approach 1: Greedy Coloring Approach (O(n + p) time, O(n + p) space)
This problem reduces to a small-scale graph coloring task. Each garden is a node and each path represents an edge. Because the constraint guarantees that every garden has at most 3 neighbors, four flower types are always enough to color the graph. Build an adjacency list and iterate through each garden. For the current garden, check the flower types already assigned to its neighbors, mark them as unavailable, and choose any remaining type from 1..4. This greedy assignment works because at most three colors can be blocked at any step.
The key insight is that the degree of each node is ≤ 3, so at least one of the four colors will always remain valid. No backtracking is required. Each edge is processed when building the adjacency list and each node checks at most three neighbors, giving O(n + p) time where p is the number of paths. This approach directly models the problem as a graph coloring task and is the simplest and fastest implementation.
Approach 2: Depth-First Search (DFS) Coloring (O(n + p) time, O(n + p) space)
A traversal-based approach uses Depth-First Search to color the graph while exploring connected components. Construct an adjacency list, then start DFS from any uncolored garden. When visiting a node, inspect the colors of its neighbors and pick the first valid flower type not already used. Continue recursively for all adjacent gardens until the component is fully colored.
This method is useful when you want a general graph traversal framework that works even if the graph has multiple disconnected components. The DFS ensures every node is visited once and every edge is considered during traversal. The complexity remains O(n + p) time with O(n + p) space due to the adjacency list and recursion stack. A similar traversal could also be implemented using Breadth-First Search.
Recommended for interviews: The Greedy Coloring approach is what most interviewers expect. It shows you recognized the degree constraint and simplified the problem into a deterministic graph coloring step without recursion. Implementing DFS still demonstrates strong understanding of graph traversal, but the greedy solution highlights the key observation that four colors always guarantee a valid assignment.
Approach 1: Greedy Coloring Approach
This approach involves using a greedy algorithm to assign a flower type to each garden. Since each garden can have at most 3 neighbors, we have a maximum degree of 3, making it feasible to find a suitable flower type from 4 options.
We traverse each garden and assign a flower type that is different from its connected gardens. Since a maximum of 3 colors (flowers) are unavailable from any adjacent gardens, there will always be at least one flower type left to choose from.
from collections import defaultdict
def gardenNoAdj(n, paths):
graph = defaultdict(list)
for x, y in paths:
graph[x - 1].append(y - 1)
graph[y - 1].append(x - 1)
answer = [0] * n
for garden in range(n):
used = {answer[neighbor] for neighbor in graph[garden]}
answer[garden] = next(fl for fl in range(1, 5) if fl not in used)
return answerimport java.util.*;
class Solution {
public int[] gardenNoAdj(int n, int[][] paths) {
int[] types = new int[n];
HashMap<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.put(i, new ArrayList<>());
}
for (int[] path : paths) {
graph.get(path[0] - 1).add(path[1] - 1);
graph.get(path[1] - 1).add(path[0] - 1);
}
for (int i = 0; i < n; i++) {
boolean[] used = new boolean[5];
for (int adj : graph.get(i)) {
used[types[adj]] = true;
}
for (int j = 1; j <= 4; j++) {
if (!used[j]) {
types[i] = j;
break;
}
}
}
return types;
}
}#include <vector>
#include <unordered_map>
using namespace std;
vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
vector<int> answer(n, 0);
unordered_map<int, vector<int>> graph;
for (auto& path : paths) {
graph[path[0] - 1].push_back(path[1] - 1);
graph[path[1] - 1].push_back(path[0] - 1);
}
for (int i = 0; i < n; ++i) {
vector<int> used(5, 0);
for (int neighbor : graph[i]) {
used[answer[neighbor]] = 1;
}
for (int color = 1; color <= 4; ++color) {
if (!used[color]) {
answer[i] = color;
break;
}
}
}
return answer;
}var gardenNoAdj = function(n, paths) {
let res = Array(n).fill(0);
let graph = Array.from({ length: n }, () => []);
for (let [u, v] of paths) {
graph[u - 1].push(v - 1);
graph[v - 1].push(u - 1);
}
for (let i = 0; i < n; ++i) {
let used = new Set();
for (let nei of graph[i]) {
used.add(res[nei]);
}
for (let j = 1; j <= 4; ++j) {
if (!used.has(j)) {
res[i] = j;
break;
}
}
}
return res;
};#include <stdio.h>
#include <stdlib.h>
int* gardenNoAdj(int n, int** paths, int pathsSize, int* pathsColSize, int* returnSize) {
*returnSize = n;
int* flowerType = (int*)calloc(n, sizeof(int));
int graph[n][3];
for (int i = 0; i < n; ++i) {
for(int j = 0; j < 3; j++)
graph[i][j] = 0;
}
for (int i = 0; i < pathsSize; ++i) {
int u = paths[i][0] - 1;
int v = paths[i][1] - 1;
for (int j = 0; j < 3; ++j) {
if (graph[u][j] == 0) {
graph[u][j] = v + 1;
break;
}
}
for (int j = 0; j < 3; ++j) {
if (graph[v][j] == 0) {
graph[v][j] = u + 1;
break;
}
}
}
for (int i = 0; i < n; ++i) {
int used[5] = {0};
for (int j = 0; j < 3 && graph[i][j]; ++j) {
used[flowerType[graph[i][j] - 1]] = 1;
}
for (int j = 1; j <= 4; ++j) {
if (!used[j]) {
flowerType[i] = j;
break;
}
}
}
return flowerType;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] GardenNoAdj(int n, int[][] paths) {
int[] result = new int[n];
Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
for (int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach (var path in paths) {
graph[path[0] - 1].Add(path[1] - 1);
graph[path[1] - 1].Add(path[0] - 1);
}
for (int i = 0; i < n; i++) {
bool[] used = new bool[5];
foreach (int neighbor in graph[i]) {
used[result[neighbor]] = true;
}
for (int j = 1; j <= 4; j++) {
if (!used[j]) {
result[i] = j;
break;
}
}
}
return result;
}
}The Python solution employs a defaultdict to store the adjacency list of gardens. It assigns each garden a flower type by evaluating its neighboring gardens, ensuring the chosen type is different from those already used by its neighbors.
Time Complexity: O(N + E), where N is the number of gardens and E is the number of paths. This accounts for the traversal of each garden and checking neighbors.
Space Complexity: O(N + E), space is needed to maintain the graph's adjacency list and the answer list of flower types.
Approach 2: Depth-First Search (DFS) Approach
This approach utilizes DFS to traverse through each garden from 1 to N. During the DFS traversal, each garden is visited, and an available flower type is assigned that’s different from its neighbor gardens. The recursion carries the assigned value to every adjacent garden, ensuring no conflicts occur.
Though DFS might not be as efficient as a greedy approach generally, it's effective here because of the specific constraints that at most 3 paths per garden exist, and because of the graph's structure.
def gardenNoAdj(n, paths):
import collections
graph = collections.defaultdict(list)
for u, v in paths:
graph[u - 1].append(v - 1)
graph[v - 1].append(u - 1)
flowers = [0] * n
def dfs(garden):
used = {flowers[nei] for nei in graph[garden] if flowers[nei]}
flowers[garden] = next(k for k in range(1, 5) if k not in used)
for nei in graph[garden]:
if not flowers[nei]:
dfs(nei)
for garden in range(n):
if not flowers[garden]:
dfs(garden)
return flowersimport java.util.*;
class Solution {
public int[] gardenNoAdj(int n, int[][] paths) {
List<Integer>[] graph = new List[n];
for(int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for(int[] path : paths) {
graph[path[0] - 1].add(path[1] - 1);
graph[path[1] - 1].add(path[0] - 1);
}
int[] flowerTypes = new int[n];
for(int garden = 0; garden < n; garden++) {
if(flowerTypes[garden] == 0) {
dfs(garden, graph, flowerTypes);
}
}
return flowerTypes;
}
private void dfs(int garden, List<Integer>[] graph, int[] flowerTypes) {
boolean[] used = new boolean[5];
for(int neighbor : graph[garden]) {
if(flowerTypes[neighbor] != 0) {
used[flowerTypes[neighbor]] = true;
}
}
for(int type = 1; type <= 4; type++) {
if(!used[type]) {
flowerTypes[garden] = type;
break;
}
}
for(int neighbor : graph[garden]) {
if(flowerTypes[neighbor] == 0) {
dfs(neighbor, graph, flowerTypes);
}
}
}
}#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
void dfs(int garden, vector<vector<int>>& graph, vector<int>& flowerTypes) {
unordered_set<int> used;
for (int neighbor : graph[garden]) {
if (flowerTypes[neighbor] != 0)
used.insert(flowerTypes[neighbor]);
}
for (int type = 1; type <= 4; ++type) {
if (!used.count(type)) {
flowerTypes[garden] = type;
break;
}
}
for (int neighbor : graph[garden]) {
if (flowerTypes[neighbor] == 0) {
dfs(neighbor, graph, flowerTypes);
}
}
}
vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
vector<vector<int>> graph(n);
vector<int> flowerTypes(n, 0);
for (auto& path : paths) {
graph[path[0] - 1].push_back(path[1] - 1);
graph[path[1] - 1].push_back(path[0] - 1);
}
for (int garden = 0; garden < n; ++garden) {
if (flowerTypes[garden] == 0) {
dfs(garden, graph, flowerTypes);
}
}
return flowerTypes;
}
};var gardenNoAdj = function(n, paths) {
let graph = Array.from({ length: n }, () => []);
for (let [u, v] of paths) {
graph[u - 1].push(v - 1);
graph[v - 1].push(u - 1);
}
let flowers = Array(n).fill(0);
function dfs(garden) {
let used = new Set(graph[garden].map(nei => flowers[nei]));
for (let i = 1; i <= 4; i++) {
if (!used.has(i)) {
flowers[garden] = i;
break;
}
}
for (let nei of graph[garden]) {
if (flowers[nei] === 0) {
dfs(nei);
}
}
}
for (let i = 0; i < n; ++i) {
if (flowers[i] === 0) {
dfs(i);
}
}
return flowers;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void dfs(int* graph[], int* flowers, int garden, int n) {
bool used[5] = {false};
for (int i = 0; i < n; i++) {
if (graph[garden][i] != -1 && flowers[graph[garden][i]] != 0) {
used[flowers[graph[garden][i]]] = true;
}
}
for (int flower = 1; flower <= 4; flower++) {
if (!used[flower]) {
flowers[garden] = flower;
break;
}
}
for (int i = 0; i < n; i++) {
if (graph[garden][i] != -1 && flowers[graph[garden][i]] == 0) {
dfs(graph, flowers, graph[garden][i], n);
}
}
}
int* gardenNoAdj(int n, int** paths, int pathsSize, int* pathsColSize, int* returnSize) {
*returnSize = n;
int** graph = malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
graph[i] = malloc(n * sizeof(int));
for(int j = 0; j < n; j++) {
graph[i][j] = -1;
}
}
int* flowers = calloc(n, sizeof(int));
for (int i = 0; i < pathsSize; ++i) {
graph[paths[i][0] - 1][paths[i][1] - 1] = paths[i][1] - 1;
graph[paths[i][1] - 1][paths[i][0] - 1] = paths[i][0] - 1;
}
for (int garden = 0; garden < n; garden++) {
if (flowers[garden] == 0) {
dfs(graph, flowers, garden, n);
}
}
for(int i = 0; i < n; i++)
free(graph[i]);
free(graph);
return flowers;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] GardenNoAdj(int n, int[][] paths) {
List<int>[] graph = new List<int>[n];
for(int i = 0; i < n; i++) {
graph[i] = new List<int>();
}
foreach(var path in paths) {
graph[path[0] - 1].Add(path[1] - 1);
graph[path[1] - 1].Add(path[0] - 1);
}
int[] flowerTypes = new int[n];
for(int garden = 0; garden < n; garden++) {
if(flowerTypes[garden] == 0) {
Dfs(garden, graph, flowerTypes);
}
}
return flowerTypes;
}
private void Dfs(int garden, List<int>[] graph, int[] flowerTypes) {
bool[] used = new bool[5];
foreach(int neighbor in graph[garden]) {
if(flowerTypes[neighbor] != 0) {
used[flowerTypes[neighbor]] = true;
}
}
for(int type = 1; type <= 4; type++) {
if(!used[type]) {
flowerTypes[garden] = type;
break;
}
}
foreach(int neighbor in graph[garden]) {
if(flowerTypes[neighbor] == 0) {
Dfs(neighbor, graph, flowerTypes);
}
}
}
}The Python implementation employs DFS by creating a graph adjacency list with defaultdict. Each garden uses recursion to assign valid flower types amongst its neighbors, ensuring valid assignments across the structure.
Time Complexity: O(N + E), due to the DFS traversal of gardens and path edges.
Space Complexity: O(N), attributed to the recursion stack and adjacency representations.
Approach 3: Enumeration
We first construct a graph g based on the array paths, where g[x] represents the list of gardens adjacent to garden x.
Next, for each garden x, we first find the gardens y adjacent to x and mark the types of flowers planted in garden y as used. Then, we enumerate the flower types starting from 1 until we find a flower type c that has not been used. We assign c as the flower type for garden x and continue to the next garden.
After the enumeration is complete, we return the result.
The time complexity is O(n + m), and the space complexity is O(n + m), where n is the number of gardens and m is the number of paths.
function gardenNoAdj(n: number, paths: number[][]): number[] {
const g: number[][] = Array.from({ length: n }, () => []);
for (const [x, y] of paths) {
g[x - 1].push(y - 1);
g[y - 1].push(x - 1);
}
const ans: number[] = Array(n).fill(0);
for (let x = 0; x < n; ++x) {
const used: boolean[] = Array(5).fill(false);
for (const y of g[x]) {
used[ans[y]] = true;
}
for (let c = 1; c < 5; ++c) {
if (!used[c]) {
ans[x] = c;
break;
}
}
}
return ans;
}func gardenNoAdj(n int, paths [][]int) []int {
g := make([][]int, n)
for _, p := range paths {
x, y := p[0]-1, p[1]-1
g[x] = append(g[x], y)
g[y] = append(g[y], x)
}
ans := make([]int, n)
for x := 0; x < n; x++ {
used := [5]bool{}
for _, y := range g[x] {
used[ans[y]] = true
}
for c := 1; c < 5; c++ {
if !used[c] {
ans[x] = c
break
}
}
}
return ans
}impl Solution {
pub fn garden_no_adj(n: i32, paths: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
let mut g = vec![vec![]; n];
for path in paths {
let (x, y) = (path[0] as usize - 1, path[1] as usize - 1);
g[x].push(y);
g[y].push(x);
}
let mut ans = vec![0; n];
for x in 0..n {
let mut used = [false; 5];
for &y in &g[x] {
used[ans[y] as usize] = true;
}
for c in 1..5 {
if !used[c] {
ans[x] = c as i32;
break;
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Coloring Approach | Time Complexity: O(N + E), where N is the number of gardens and E is the number of paths. This accounts for the traversal of each garden and checking neighbors. Space Complexity: O(N + E), space is needed to maintain the graph's adjacency list and the answer list of flower types. |
| Depth-First Search (DFS) Approach | Time Complexity: O(N + E), due to the DFS traversal of gardens and path edges. Space Complexity: O(N), attributed to the recursion stack and adjacency representations. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Coloring | O(n + p) | O(n + p) | Best choice when node degree is small and a fixed number of colors guarantees a solution |
| Depth-First Search (DFS) Coloring | O(n + p) | O(n + p) | Useful when applying a standard graph traversal or handling multiple disconnected components |
Frequently asked questions
Is Flower Planting With No Adjacent easy or hard?
The problem is rated Medium on LeetCode. The implementation is straightforward once you recognize it as a graph coloring problem with a small fixed color set. The main challenge is identifying the constraint that each garden has at most three neighbors, which guarantees a greedy solution.
How to solve Flower Planting With No Adjacent in O(n)?
Treat gardens as nodes in a graph and paths as edges. Build an adjacency list, iterate through each garden, and track flower types already used by its neighbors. Assign the first available flower from 1 to 4. Because each node has at most three neighbors, this greedy step always succeeds and runs in O(n + p) time.
Flower Planting With No Adjacent Python or Java solution?
Most implementations build an adjacency list and maintain an array of size n for flower assignments. For each garden, iterate through neighbors, mark their flower types as used, and choose a remaining type. The same greedy logic works across Python, Java, C++, JavaScript, and other languages.
What is the best approach for Flower Planting With No Adjacent?
The greedy graph coloring approach is the most efficient and simplest solution. Each garden has at most three neighbors, so among four flower types at least one will always be available. By checking the colors of adjacent gardens and choosing an unused one, you solve the problem in O(n + p) time without backtracking.
What data structure is used in Flower Planting With No Adjacent?
The primary data structure is an adjacency list representing the graph of gardens and paths. Arrays or lists store neighbors for each garden, and another array tracks the assigned flower type. DFS or BFS traversal can also be applied using recursion or a queue.
What is the time complexity of Flower Planting With No Adjacent?
The optimal solution runs in O(n + p) time where n is the number of gardens and p is the number of paths. Building the adjacency list processes each edge once, and each garden checks at most three neighbors when selecting a flower type. Space complexity is also O(n + p) due to the adjacency list.
Is Flower Planting With No Adjacent asked at Google, Amazon, or Meta?
Graph coloring and traversal problems similar to this appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, recognizing graph modeling, adjacency lists, and greedy coloring strategies is commonly tested in technical interviews.