Skip to main content
Talentd

Divide Nodes Into the Maximum Number of Groups - Solution & Explanation

HardBreadth-First SearchUnion FindGraph18 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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.

 

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 <= 104
  • edges[i].length == 2
  • 1 <= ai, bi <= n
  • ai != bi
  • There is at most one edge between any pair of vertices.

Approach Overview

Problem 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 1: Using Bipartite Graph Check

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Graph Traversal with DFS

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.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n + m), traversing each edge and node once.
Space Complexity: O(n + m) for stack space and graph storage.

Try this approach in the editor →

Approach 3: BFS + Enumeration

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.

Code

PythonJavaC++GoJavaScript

Python

Java

C++

Go

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n + m) for storing the graph and queue.

Graph Traversal with DFS

Time Complexity: O(n + m), traversing each edge and node once.
Space Complexity: O(n + m) for stack space and graph storage.

BFS + Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bipartite Graph Check with BFS LevelsO(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 DepthO(n * (n + m))O(n + m)Useful when you want explicit component discovery with DFS and then measure grouping depth using BFS.

Video Solution

Divide Nodes Into the Maximum Number of Groups - Leetcode 2493 - Python • NeetCodeIO • 12,489 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Divide Nodes Into the Maximum Number of Groups easy or hard?
Divide Nodes Into the Maximum Number of Groups is classified as Hard on LeetCode. The difficulty comes from recognizing the bipartite constraint and combining it with BFS level analysis across connected components.
Divide Nodes Into the Maximum Number of Groups Python/Java solution
Most implementations build an adjacency list, verify the graph is bipartite using BFS, and then compute maximum BFS depth within each connected component. Python solutions typically use collections.deque for BFS queues, while Java solutions rely on ArrayDeque or LinkedList.
How to solve Divide Nodes Into the Maximum Number of Groups in O(n)?
A strict O(n) solution is not typical because the algorithm requires BFS traversals across graph components. The closest efficient method is O(n + m) for bipartite checking plus repeated BFS explorations, resulting in O(n * (n + m)) in the worst case. This ensures all possible BFS roots are evaluated for maximum group depth.
What is the best approach for Divide Nodes Into the Maximum Number of Groups?
The best approach is checking whether the graph is bipartite and then computing BFS levels for each node within a connected component. BFS naturally assigns increasing levels to neighbors, which represent valid group indices. The maximum level count found in each component determines the number of groups. This solution runs in O(n * (n + m)) time.
Is Divide Nodes Into the Maximum Number of Groups asked at Google/Amazon/Meta?
Graph traversal and bipartite validation problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants involving BFS layering, odd-cycle detection, and component analysis are common in system design and algorithm rounds.
What data structure is used in Divide Nodes Into the Maximum Number of Groups?
The solution primarily uses an adjacency list to represent the graph, along with a queue for Breadth-First Search. Arrays or hash maps track visited nodes and group levels. Bipartite coloring also uses simple arrays to store node colors.
What is the time complexity of Divide Nodes Into the Maximum Number of Groups?
The overall time complexity is O(n * (n + m)), where n is the number of nodes and m is the number of edges. BFS may run once from every node inside a component to compute the maximum depth. Space complexity is O(n + m) for the adjacency list and traversal structures.

Ready to solve this problem?

Practice Divide Nodes Into the Maximum Number of Groups with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Level Order Traversal

Next

Is Graph Bipartite?