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.
The problem can be visualized as checking if the graph is bipartite for each connected component. If a graph is bipartite, it can be colored with two colors such that no two adjacent nodes have the same color, which allows us to divide the nodes into two groups. The maximum number of groups will then depend on the maximum height of such a bipartite division across all disconnected components.
The solution involves constructing the graph using adjacency lists and then using BFS (Breadth-First Search) to color each component, starting from an unvisited node. We use BFS to check if each connected component is bipartite by attempting to color it with two colors (0 and 1). If a conflict is encountered, the graph is not bipartite, and -1 is returned.
If the component is bipartite, we compute the height of the tree from one node, which gives us the number of groups possible for that component. This process is repeated for each component, updating the maximum possible number of groups across all components.
Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges, as we traverse each node and edge at most once.
Space Complexity: O(n + m) for storing the graph and queue.
Another approach is using Depth-First Search (DFS) to explore each component of the graph and determine its bipartiteness. The idea is similar to the first approach but utilizes a stack-based DFS approach to explore nodes and color them to check for possibilities of dividing into groups.
We use a stack to implement DFS for each unvisited node to evaluate the graph's component for bipartiteness. We color nodes alternatively and push them onto the stack for further exploration, determining if the graph can be divided into two-color groups. If a node attempts to color adjacent nodes with the same color it has, then the graph or component cannot be bipartite, and we return -1.
The depth reached in DFS gives us an insight into the maximum number of groups possible for that component.
C++
JavaScript
Time Complexity: O(n + m), traversing each edge and node once.
Space Complexity: O(n + m) for stack space and graph storage.
Given that the graph provided by the problem may be disconnected, we need to process each connected component, find the maximum number of groups in each connected component, and accumulate them to get the final result.
We can enumerate each node as the node of the first group, then use BFS to traverse the entire connected component, and use an array d to record the maximum number of groups in each connected component. In the code implementation, we use the smallest node in the connected component as the root node of this connected component.
During the BFS process, we use a queue q to store the nodes currently traversed, use an array dist to record the distance from each node to the starting node, use a variable mx to record the maximum depth of the current connected component, and use a variable root to record the root node of the current connected component.
During the traversal, if we find that the dist[b] of a certain node b is 0, it means that b has not been traversed yet. We set the distance of b to dist[a] + 1, update mx, and add b to the queue q. If the distance of b has been updated, we check whether the distance between b and a is 1. If not, it means that the problem requirements cannot be met, so we directly return -1.
The time complexity is O(n times (n + m)), and the space complexity is O(n + m). Where n and m are the number of nodes and edges respectively.
Python
Java
C++
Go
JavaScript
| Approach | Complexity |
|---|---|
| Using Bipartite Graph Check | Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges, as we traverse each node and edge at most once. |
| Graph Traversal with DFS | Time Complexity: O(n + m), traversing each edge and node once. |
| BFS + Enumeration | — |
| 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. |
Divide Nodes Into the Maximum Number of Groups - Leetcode 2493 - Python • NeetCodeIO • 12,274 views views
Watch 9 more video solutions →Practice Divide Nodes Into the Maximum Number of Groups with our built-in code editor and test cases.
Practice on FleetCode