Divide Nodes Into the Maximum Number of Groups

Hard

#2275Time: O(n^n * E)Space: O(n)

Algorithms

Depth-First Search Breadth-First Search Union Find

Data structures

Prompt

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] = [a_i,b_i] indicates that there is a bidirectional edge between nodes a_i and b_i. 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 [a_i,b_i], if a_i belongs to the group with index x, and b_i 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.

Example 1:

Input: n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]
Output: 4
Explanation: As shown in the image we:
- Add node 5 to the first group.
- Add node 1 to the second group.
- Add nodes 2 and 4 to the third group.
- Add nodes 3 and 6 to the fourth group.
We can see that every edge is satisfied.
It can be shown that that if we create a fifth group and move any node from the third or fourth group to it, at least on of the edges will not be satisfied.

Example 2:

Input: n = 3, edges = [[1,2],[2,3],[3,1]]
Output: -1
Explanation: If we add node 1 to the first group, node 2 to the second group, and node 3 to the third group to satisfy the first two edges, we can see that the third edge will not be satisfied.
It can be shown that no grouping is possible.

Constraints:

1 <= n <= 500
1 <= edges.length <= 10⁴
edges[i].length == 2
1 <= a_i, b_i <= n
a_i != b_i
There is at most one edge between any pair of vertices.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring every possible assignment of nodes to groups. It uses a backtracking algorithm to systematically try all combinations. For each node, it tries to place it in a group and then recursively moves to the next node. If an assignment for all nodes is found that satisfies the given edge conditions, it calculates the number of groups used and updates a global maximum.

Algorithm

Define a recursive function, say solve(nodeIndex, assignments), where assignments stores the group for each assigned node.
Base Case: If nodeIndex is greater than n, all nodes have been assigned. Check if the current assignment is valid by iterating through all edges. If it is, update the maximum number of groups found so far. The number of groups is max(assignments) - min(assignments) + 1.
Recursive Step: For the current nodeIndex, iterate through all possible group numbers g (e.g., from 1 to n).
- Assign nodeIndex to group g.
- As a small optimization (pruning), check if this assignment violates the condition with any already-assigned neighbors. If it does, skip this group g.
- If the partial assignment is valid, make a recursive call: solve(nodeIndex + 1, assignments).
- Backtrack by removing the assignment for nodeIndex before trying the next group.

Walkthrough

The core idea of the backtracking approach is to build a valid group assignment for the nodes one by one. We can define a recursive function that takes the index of the node to be assigned and the current state of assignments.

For each node, we try to assign it to a group. After assigning a group, we recursively call the function for the next node. If we have assigned groups to all nodes, we check if the complete assignment is valid according to the problem's rules. If it is, we compute the number of groups used and update our answer. If at any point an assignment leads to a state where a valid solution is impossible (e.g., an edge constraint is violated with already placed nodes), we backtrack and try a different group.

While this approach is guaranteed to find the correct answer eventually, its search space is enormous. For n nodes and potentially n groups, the number of combinations is n^n, leading to an exponential time complexity that is not practical for the given constraints.

Complexity

Time

O(n^n * E)

Space

O(n)

Trade-offs

Pros

Conceptually straightforward and follows a standard brute-force pattern.

Cons

Extremely high time complexity, making it infeasible for the given constraints.
Will result in a 'Time Limit Exceeded' (TLE) error on most platforms.

This efficient approach leverages graph theory concepts. It understands that the condition |y - x| = 1 for adjacent nodes implies that any valid grouping is impossible if the graph contains an odd-length cycle (i.e., is not bipartite). The problem can be solved independently for each connected component of the graph. For each component, we first check if it's bipartite. If not, we return -1. If it is, the maximum number of groups we can form within that component is equal to its diameter plus one. The final answer is the sum of the maximum groups for each component.

Algorithm

Graph Representation: Build an adjacency list for the graph from the edges array.
Component Iteration: Initialize totalMaxGroups = 0 and a colors array (or visited array) of size n+1 to keep track of visited nodes and their colors for the bipartite check.
Iterate through each node from 1 to n. If a node i has not been visited (colors[i] == 0), it signifies the start of a new connected component.
Bipartite Check: For each new component, perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from node i.
- During the traversal, assign one of two colors (e.g., 1 and -1) to the nodes. If you find an edge (u, v) where both nodes have the same color, the graph contains an odd-length cycle and is not bipartite. In this case, no valid grouping is possible, so return -1.
- While performing this check, collect all nodes belonging to the current component into a list.
Diameter Calculation: If the component is bipartite, calculate its diameter. The diameter is the longest shortest path between any two nodes in the component.
- Initialize componentDiameter = 0.
- For each startNode in the component's node list, run a BFS to find the shortest distance to all other nodes in the component. The maximum distance found is the eccentricity of startNode.
- Update componentDiameter with the maximum eccentricity found among all nodes in the component.
Aggregate Results: The maximum number of groups for the current component is componentDiameter + 1. Add this value to totalMaxGroups.
Final Result: After iterating through all components, return totalMaxGroups.

Walkthrough

A deeper analysis of the constraint |group(u) - group(v)| = 1 for every edge (u, v) reveals key properties of the graph.

Bipartiteness: This condition implies that adjacent nodes must have group numbers of different parity. This is the definition of a 2-coloring, which is possible only if the graph is bipartite (contains no odd-length cycles). If any connected component is not bipartite, no such grouping exists, and we must return -1.
Connected Components: Since there are no edges between different connected components, we can solve the problem for each component independently and sum the results. If component C1 can be divided into m1 groups and C2 into m2 groups, we can assign groups 1...m1 to C1 and m1+1...m1+m2 to C2, for a total of m1+m2 groups.
Diameter and Maximum Groups: For a connected bipartite component, we can define a valid grouping by picking a starting node s and setting group(u) = distance(s, u) + 1. The number of groups will be eccentricity(s) + 1. To maximize the number of groups, we need to find a starting node s that maximizes this value. This is equivalent to finding the graph's diameter, which is the maximum eccentricity over all nodes. The maximum number of groups for a component is diameter + 1.

The overall algorithm is as follows:

1class Solution {2    public int magnificentSets(int n, int[][] edges) {3        List<Integer>[] adj = new ArrayList[n + 1];4        for (int i = 1; i <= n; i++) {5            adj[i] = new ArrayList<>();6        }7        for (int[] edge : edges) {8            adj[edge[0]].add(edge[1]);9            adj[edge[1]].add(edge[0]);10        }11 12        int[] colors = new int[n + 1]; // 0: uncolored, 1/-1: colors13        int totalMaxGroups = 0;14 15        for (int i = 1; i <= n; i++) {16            if (colors[i] == 0) { // New component17                List<Integer> componentNodes = new ArrayList<>();18                19                if (!isBipartiteAndCollectNodes(i, adj, colors, componentNodes)) {20                    return -1;21                }22 23                int maxLevels = 0;24                for (int startNode : componentNodes) {25                    int currentLevels = bfsToFindMaxLevel(startNode, adj, componentNodes);26                    maxLevels = Math.max(maxLevels, currentLevels);27                }28                totalMaxGroups += maxLevels;29            }30        }31        return totalMaxGroups;32    }33 34    private boolean isBipartiteAndCollectNodes(int startNode, List<Integer>[] adj, int[] colors, List<Integer> componentNodes) {35        Queue<Integer> q = new LinkedList<>();36        q.offer(startNode);37        colors[startNode] = 1;38        39        componentNodes.add(startNode);40        int head = 0;41 42        while(head < componentNodes.size()){43            int u = componentNodes.get(head++);44            for(int v : adj[u]){45                if(colors[v] == 0){46                    colors[v] = -colors[u];47                    componentNodes.add(v);48                } else if (colors[v] == colors[u]){49                    return false; // Not bipartite50                }51            }52        }53        return true;54    }55 56    private int bfsToFindMaxLevel(int startNode, List<Integer>[] adj, List<Integer> componentNodes) {57        Queue<int[]> q = new LinkedList<>(); // {node, level}58        q.offer(new int[]{startNode, 1});59        60        Map<Integer, Integer> levels = new HashMap<>();61        levels.put(startNode, 1);62        63        int maxLevel = 0;64 65        while (!q.isEmpty()) {66            int[] current = q.poll();67            int u = current[0];68            int level = current[1];69            maxLevel = Math.max(maxLevel, level);70 71            for (int v : adj[u]) {72                if (!levels.containsKey(v)) {73                    levels.put(v, level + 1);74                    q.offer(new int[]{v, level + 1});75                }76            }77        }78        return maxLevel;79    }80}

Complexity

Time

O(V * (V + E)). For each component with `v_c` nodes and `e_c` edges, we do a bipartite check in `O(v_c + e_c)` and then `v_c` BFS runs for diameter, each taking `O(v_c + e_c)`. Summing over all components, the worst case is a single connected graph, leading to `O(V * (V + E))`.

Space

O(V + E) for the adjacency list, colors array, and BFS queue.

Trade-offs

Pros

Correctly models the problem using graph properties.
Guaranteed to find the optimal solution.
Efficient enough to pass the given constraints.

Cons

The implementation is more complex than a simple brute-force approach.
The time complexity of O(V * (V + E)) might be too slow for significantly larger graphs, although it passes the given constraints.

Solutions

Solution

1class Solution {2private3  List<Integer>[] g;4private5  List<Integer> arr = new ArrayList<>();6private7  boolean[] vis;8private9  int n;10public11  int magnificentSets(int n, int[][] edges) {12    g = new List[n + 1];13    this.n = n;14    Arrays.setAll(g, k->new ArrayList<>());15    for (var e : edges) {16      int a = e[0], b = e[1];17      g[a].add(b);18      g[b].add(a);19    }20    vis = new boolean[n + 1];21    int ans = 0;22    for (int i = 1; i <= n; ++i) {23      if (!vis[i]) {24        dfs(i);25        int t = -1;26        for (int v : arr) {27          t = Math.max(t, bfs(v));28        }29        if (t == -1) {30          return -1;31        }32        ans += t;33        arr.clear();34      }35    }36    return ans;37  }38private39  int bfs(int k) {40    int[] dist = new int[n + 1];41    Arrays.fill(dist, 1 << 30);42    dist[k] = 1;43    Deque<Integer> q = new ArrayDeque<>();44    q.offer(k);45    int ans = 1;46    while (!q.isEmpty()) {47      int i = q.pollFirst();48      for (int j : g[i]) {49        if (dist[j] == 1 << 30) {50          dist[j] = dist[i] + 1;51          ans = dist[j];52          q.offer(j);53        }54      }55    }56    for (int i : arr) {57      if (dist[i] == 1 << 30) {58        dist[i] = ++ans;59      }60    }61    for (int i : arr) {62      for (int j : g[i]) {63        if (Math.abs(dist[i] - dist[j]) != 1) {64          return -1;65        }66      }67    }68    return ans;69  }70private71  void dfs(int i) {72    arr.add(i);73    vis[i] = true;74    for (int j : g[i]) {75      if (!vis[j]) {76        dfs(j);77      }78    }79  }80}

1var magnificentSets = function ( n , edges ) { const graph = Array . from ({ length : n + 1 }, () => new Set ()); for ( const [ u , v ] of edges ) { graph [ u ]. add ( v ); graph [ v ]. add ( u ); } const hash = new Map (); // 2. BFS for ( let i = 1 ; i <= n ; i ++ ) { let queue = [ i ]; const dis = Array ( n + 1 ). fill ( 0 ); dis [ i ] = 1 ; let mx = 1 , mn = n ; while ( queue . length ) { let next = []; for ( let u of queue ) { mn = Math . min ( mn , u ); for ( const v of graph [ u ]) { if ( ! dis [ v ]) { dis [ v ] = dis [ u ] + 1 ; mx = Math . max ( mx , dis [ v ]); next . push ( v ); } if ( Math . abs ( dis [ u ] - dis [ v ]) != 1 ) { return - 1 ; } } } queue = next ; } hash . set ( mn , Math . max ( mx , hash . get ( mn ) || 0 )); } let ans = 0 ; for ( const [ u , v ] of hash ) { ans += v ; } return ans ; };

1class Solution {2public:3  int magnificentSets(int n, vector<vector<int>> &edges) {4    vector<vector<int>> g(n + 1);5    for (auto &e : edges) {6      int a = e[0], b = e[1];7      g[a].emplace_back(b);8      g[b].emplace_back(a);9    }10    vector<int> arr;11    bool vis[n + 1];12    memset(vis, 0, sizeof vis);13    int ans = 0;14    function<void(int)> dfs = [&](int i) {15      arr.emplace_back(i);16      vis[i] = true;17      for (int &j : g[i]) {18        if (!vis[j]) {19          dfs(j);20        }21      }22    };23    auto bfs = [&](int k) {24      int ans = 1;25      int dist[n + 1];26      memset(dist, 0x3f, sizeof dist);27      dist[k] = 1;28      queue<int> q{{k}};29      while (!q.empty()) {30        int i = q.front();31        q.pop();32        for (int &j : g[i]) {33          if (dist[j] == 0x3f3f3f3f) {34            ans = dist[j] = dist[i] + 1;35            q.push(j);36          }37        }38      }39      for (int &i : arr) {40        if (dist[i] == 0x3f3f3f3f) {41          dist[i] = ++ans;42        }43      }44      for (int &i : arr) {45        for (int &j : g[i]) {46          if (abs(dist[i] - dist[j]) != 1) {47            return -1;48          }49        }50      }51      return ans;52    };53    for (int i = 1; i <= n; ++i) {54      if (!vis[i]) {55        dfs(i);56        int t = -1;57        for (int &v : arr)58          t = max(t, bfs(v));59        if (t == -1)60          return -1;61        ans += t;62        arr.clear();63      }64    }65    return ans;66  }67};

1class Solution:2    def magnificentSets(self, n: int, edges: List[List[int]]) -> int: def dfs(i): arr . append(i) vis[i] = True for j in g[i]: if not vis[j]: dfs(j) def bfs(i): ans = 1 dist = [inf] * (n + 1) dist[i] = 1 q = deque([i]) while q: i = q . popleft() for j in g[i]: if dist[j] == inf: ans = dist[j] = dist[i] + 1 q . append(j) for i in arr: if dist[i] == inf: ans += 1 dist[i] = ans for i in arr: for j in g[i]: if abs(dist[i] - dist[j]) != 1: return - 1 return ans g = defaultdict(list) for a, b in edges: g[a]. append(b) g[b]. append(a) vis = [False] * (n + 1) ans = 0 for i in range(1, n + 1): if not vis[i]: arr = [] dfs(i) t = max(bfs(v) for v in arr) if t == - 1: return - 1 ans += t return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem