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 != biThe 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.
Java
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.
JavaScript
Time Complexity: O(n + m), traversing each edge and node once.
Space Complexity: O(n + m) for stack space and graph storage.
| 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. |
Divide Intervals Into Minimum Number of Groups - Leetcode 2406 - Python • NeetCodeIO • 11,302 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