Divide Nodes Into the Maximum Number of Groups

Divide Nodes Into the Maximum Number of Groups - Problem

You are given a positive integer n representing the number of nodes in an undirected graph. The nodes are labeled from 1 to n.

You are also given a 2D integer array edges, where edges[i] = [ai, bi] indicates that there is a bidirectional edge between nodes ai and bi. Notice that the given graph may be disconnected.

Divide the nodes of the graph into m groups (1-indexed) such that:

Each node in the graph belongs to exactly one group.
For every pair of nodes in the graph that are connected by an edge [ai, bi], if ai belongs to the group with index x, and bi belongs to the group with index y, then |y - x| = 1.

Return the maximum number of groups (i.e., maximum m) into which you can divide the nodes. Return -1 if it is impossible to group the nodes with the given conditions.

Input & Output

Example 1 — Path Graph

$ Input: n = 6, edges = [[1,2],[1,3],[2,4],[4,5],[4,6]]

› Output: 4

💡 Note: The graph forms a tree. We can assign: node 3→group 1, node 1→group 2, node 2→group 3, nodes 4→group 4. Adjacent nodes differ by exactly 1 group.

Example 2 — Triangle (Odd Cycle)

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

› Output: -1

💡 Note: This forms a triangle (3-cycle). It's impossible to assign groups where adjacent nodes always differ by 1, since we'd need 1→2→3→1 which is impossible.

Example 3 — Disconnected Components

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

› Output: 2

💡 Note: Two separate edges: 1-2 and 3-4. Each component needs 2 groups. Maximum across all components is 2.

Constraints

1 ≤ n ≤ 15
0 ≤ edges.length ≤ n * (n - 1) / 2
edges[i].length == 2
1 ≤ ai, bi ≤ n
ai ≠ bi
There are no duplicate edges.

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Undirected graph with nodes and edges

Apply Constraint

Adjacent nodes must be in consecutive groups

Find Maximum

Return highest group number possible

Key Takeaway

🎯 Key Insight: The constraint creates bipartite structure - find diameter of each component

Asked in

G Google 12 f Meta 8

This problem requires recognizing that the adjacent constraint creates a bipartite-like structure. The key insight is that if adjacent nodes must be in groups differing by exactly 1, then the graph must be bipartite (no odd cycles). The optimal approach uses BFS to check bipartiteness and find the diameter (longest path) of each component. Time: O(n²), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Groupings	O(n^n)	O(n)	Generate all possible group assignments and check validity
BFS - Check Bipartiteness and Find Diameter	O(n * (n + m))	O(n + m)	Use BFS to verify graph is bipartite, then find maximum path length

Brute Force - Try All Groupings — Algorithm Steps

Generate all possible group assignments
For each assignment, verify adjacent nodes differ by exactly 1
Return maximum valid group count or -1

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Assignment

Try assigning nodes to groups 1,2,3...

Check Constraints

Verify adjacent nodes differ by exactly 1

Track Maximum

Keep the highest valid group count

Code -

solution.c — C

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

int adj[16][16];
int adjSize[16];

int tryAssignment(int node, int* groups, int maxGroup, int n) {
    if (node > n) return 1;
    
    for (int g = 1; g <= maxGroup; g++) {
        groups[node] = g;
        int valid = 1;
        
        for (int i = 0; i < adjSize[node]; i++) {
            int neighbor = adj[node][i];
            if (neighbor < node && groups[neighbor] != 0) {
                if (abs(groups[node] - groups[neighbor]) != 1) {
                    valid = 0;
                    break;
                }
            }
        }
        
        if (valid && tryAssignment(node + 1, groups, maxGroup, n)) {
            return 1;
        }
    }
    
    groups[node] = 0;
    return 0;
}

int solution(int n, int edges[][2], int edgesSize) {
    memset(adjSize, 0, sizeof(adjSize));
    
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        adj[u][adjSize[u]++] = v;
        adj[v][adjSize[v]++] = u;
    }
    
    int maxGroups = -1;
    
    for (int maxGroup = 1; maxGroup <= n; maxGroup++) {
        int groups[16] = {0};
        if (tryAssignment(1, groups, maxGroup, n)) {
            maxGroups = maxGroup;
        }
    }
    
    return maxGroups;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    scanf(" %s", line);
    
    // Simple parsing for edges
    int edges[20][2];
    int edgesSize = 0;
    
    char* ptr = line + 1; // skip '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int u = 0, v = 0;
            while (*ptr >= '0' && *ptr <= '9') {
                u = u * 10 + (*ptr - '0');
                ptr++;
            }
            ptr++; // skip ','
            while (*ptr >= '0' && *ptr <= '9') {
                v = v * 10 + (*ptr - '0');
                ptr++;
            }
            edges[edgesSize][0] = u;
            edges[edgesSize][1] = v;
            edgesSize++;
            ptr++; // skip ']'
        } else {
            ptr++;
        }
    }
    
    int result = solution(n, edges, edgesSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n^n)

n^n possible group assignments for n nodes

✓ Linear Growth

Space Complexity

O(n)

Store current group assignment

⚡ Linearithmic Space

8.9K Views

Medium Frequency

~35 min Avg. Time

234 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

Brute Force - Try All Groupings — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler