Divide Nodes Into the Maximum Number of Groups
01 · Problem
You are given an undirected graph with n nodes labelled 1 to n (1-indexed) and a list edges, where edges[i] = [a, b] connects a and b. The graph may be disconnected.
Split all nodes into m groups numbered 1 to m so that:
- every node belongs to exactly one group, and
- for every edge
[a, b], ifais in groupxandbis in groupy, then|x - y| == 1.
Groups may not be empty. Return the largest m for which such a split exists, or -1 if no valid split exists at all.
02 · Examples
n = 5, edges = [[1,2],[2,3],[3,4]]
5
Put nodes 1, 2, 3, 4 into groups 1, 2, 3, 4 in path order, and the isolated node 5 into its own group 5. Five groups is the maximum.
n = 4, edges = [[1,2],[2,3],[3,4],[4,1]]
3
For the 4-cycle, use groups {1}, {2,4}, {3}. Every edge joins neighbouring groups, and 4 groups is impossible because 1 and 3 are only two steps apart along both sides of the cycle.
n = 3, edges = [[1,2],[2,3],[3,1]]
-1
Nodes 1, 2, 3 form a triangle. Edges force groups to alternate parity, which an odd cycle cannot do, so no valid split exists.
03 · Constraints
- 011 <= n <= 500
- 020 <= edges.length <= 104
- 03edges[i].length == 2, 1 <= a, b <= n, a != b
- 04There is at most one edge between any pair of nodes
04 · Optimal complexity
- Time
- O(n * (n + e))
- Space
- O(n + e)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.