Watch 10 video solutions for Divide Nodes Into the Maximum Number of Groups, a hard level problem involving Breadth-First Search, Union Find, Graph. This walkthrough by NeetCodeIO has 12,274 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
[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.
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 <= 5001 <= edges.length <= 104edges[i].length == 21 <= ai, bi <= nai != biProblem Overview: You are given an undirected graph with n nodes. The task is to divide nodes into the maximum number of sequential groups such that every edge connects nodes whose group indices differ by exactly 1. If the graph structure makes this impossible, return -1.
Approach 1: Bipartite Graph Check with BFS Levels (O(n * (n + m)) time, O(n + m) space)
The key observation: if adjacent nodes must differ by exactly one group index, the graph must be bipartite. Any odd cycle breaks this rule because nodes would eventually need the same level difference. First build an adjacency list and verify bipartiteness using Breadth-First Search. While traversing each connected component, run BFS from every node in that component and compute the maximum depth (level count). BFS naturally assigns increasing levels to neighbors, which directly maps to group numbers. For each component, track the largest BFS depth reachable from any node. The final answer is the sum of these maximum depths across all components.
Approach 2: Graph Traversal with DFS + Level BFS (O(n * (n + m)) time, O(n + m) space)
Another way is separating the problem into two phases. Use graph traversal with DFS to identify connected components. During DFS, also check bipartiteness by assigning alternating colors to neighbors. If a conflict appears, the graph contains an odd cycle and the answer is -1. Once a valid component is confirmed, run BFS from each node inside that component to compute the maximum number of levels achievable. This BFS layering effectively measures the longest valid grouping chain. The maximum level count inside each component contributes to the total groups.
Recommended for interviews: The BFS-based bipartite check combined with level expansion is the approach most interviewers expect. It clearly demonstrates understanding of bipartite graphs, BFS layering, and component processing. Using Union Find can help group components, but the BFS depth calculation remains the key insight. Showing the bipartite validation first proves correctness, while the repeated BFS reveals the maximum grouping structure.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bipartite Graph Check with BFS Levels | O(n * (n + m)) | O(n + m) | General case. Works well for verifying bipartite structure and computing maximum BFS layers per component. |
| DFS Component Traversal + BFS Depth | O(n * (n + m)) | O(n + m) | Useful when you want explicit component discovery with DFS and then measure grouping depth using BFS. |