Flower Planting With No Adjacent - Practice Coding Problems

Flower Planting With No Adjacent - 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 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.

Input & Output

Example 1 — Basic Connected Gardens

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

› Output: [1,2,1]

💡 Note: Garden 1 gets flower type 1, garden 2 gets type 2 (can't use 1 due to connection to garden 1), garden 3 gets type 1 (can't use 2 due to connection to garden 2, but can reuse 1)

Example 2 — Triangle Formation

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

› Output: [1,2,3,4]

💡 Note: Garden 1 is connected to all others, so gardens 2, 3, 4 each need different flower types from garden 1 and can use types 2, 3, 4 respectively

Example 3 — No Connections

$ Input: n = 4, paths = []

› Output: [1,1,1,1]

💡 Note: No paths means no restrictions, so all gardens can use the same flower type 1

Constraints

1 ≤ n ≤ 10⁴
0 ≤ paths.length ≤ 2 × 10⁴
paths[i].length == 2
1 ≤ x_i, y_i ≤ n
x_i ≠ y_i
Every garden has at most 3 paths coming into or leaving it

Visualization

Tap to expand

Understanding the Visualization

Input

Gardens connected by bidirectional paths

Process

Assign flowers ensuring adjacent gardens differ

Output

Valid flower assignment array

Key Takeaway

🎯 Key Insight: With 4 flower types and max 3 neighbors per garden, there's always a valid flower choice available

Asked in

G Google 45 f Facebook 32 a Amazon 28

This is a graph coloring problem where we need to assign one of 4 flower types to each garden such that connected gardens have different flowers. The key insight is that since each garden has at most 3 neighbors and we have 4 flower types, there's always a valid flower available. The greedy approach works optimally: build an adjacency list, then for each garden, assign the smallest flower type not used by any neighbor. Time: O(n + m), Space: O(n + m).

Common Approaches

Approach	Time	Space	Notes
✓ DFS Graph Coloring	O(n + m)	O(n + m)	Use depth-first search to traverse and color the graph components
Brute Force - Try All Combinations	O(4ⁿ × m)	O(n)	Generate all possible flower assignments and check if any is valid
Greedy Graph Coloring	O(n + m)	O(n + m)	For each garden, pick the smallest flower type not used by any neighbor

DFS Graph Coloring — Algorithm Steps

Build adjacency list from paths
For each unvisited garden, start DFS with flower type 1
Recursively color neighbors with first available non-conflicting flower

Visualization

Tap to expand

Step-by-Step Walkthrough

Start DFS

Begin from unvisited garden with flower 1

Traverse

Recursively visit and color neighbors

Complete

All connected gardens colored without conflicts

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int** graph;
int* graphSize;
int* result;

void dfs(int garden) {
    // Get flower types used by neighbors
    int used[5] = {0}; // index 1-4 for flowers
    for (int i = 0; i < graphSize[garden]; i++) {
        int neighbor = graph[garden][i];
        if (result[neighbor] != 0) {
            used[result[neighbor]] = 1;
        }
    }
    
    // Assign smallest available flower type
    for (int flower = 1; flower <= 4; flower++) {
        if (!used[flower]) {
            result[garden] = flower;
            break;
        }
    }
    
    // Recursively color uncolored neighbors
    for (int i = 0; i < graphSize[garden]; i++) {
        int neighbor = graph[garden][i];
        if (result[neighbor] == 0) {
            dfs(neighbor);
        }
    }
}

int* solution(int n, int paths[][2], int pathCount) {
    // Build adjacency list
    graph = (int**)malloc(n * sizeof(int*));
    graphSize = (int*)calloc(n, sizeof(int));
    
    // Count neighbors for each garden
    for (int i = 0; i < pathCount; i++) {
        graphSize[paths[i][0]-1]++;
        graphSize[paths[i][1]-1]++;
    }
    
    // Allocate space
    for (int i = 0; i < n; i++) {
        graph[i] = (int*)malloc(graphSize[i] * sizeof(int));
        graphSize[i] = 0; // Reset for building
    }
    
    // Build adjacency list
    for (int i = 0; i < pathCount; i++) {
        int x = paths[i][0] - 1;
        int y = paths[i][1] - 1;
        graph[x][graphSize[x]++] = y;
        graph[y][graphSize[y]++] = x;
    }
    
    result = (int*)calloc(n, sizeof(int));
    
    // Start DFS from each unvisited garden
    for (int i = 0; i < n; i++) {
        if (result[i] == 0) {
            dfs(i);
        }
    }
    
    // Free memory (except result which is returned)
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(graphSize);
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int pathCount = 0;
    for (int i = 0; line[i]; i++) {
        if (line[i] == '[' && i > 0) pathCount++;
    }
    
    int paths[100][2];
    if (pathCount > 0) {
        char* ptr = line + 1;
        for (int i = 0; i < pathCount; i++) {
            while (*ptr != '[') ptr++;
            ptr++;
            paths[i][0] = atoi(ptr);
            while (*ptr != ',') ptr++;
            ptr++;
            paths[i][1] = atoi(ptr);
            while (*ptr != ']') ptr++;
            ptr++;
        }
    }
    
    int* res = solution(n, paths, pathCount);
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("%d", res[i]);
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    free(res);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Visit each garden once O(n) and each edge twice O(2m) during DFS traversal

✓ Linear Growth

Space Complexity

O(n + m)

Adjacency list O(m) plus recursion stack depth O(n) in worst case

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS Graph Coloring — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler