2493. Divide Nodes Into the Maximum Number of Groups LeetCode Solution

Last updated: February 27, 2025

In this guide, you will get 2493. Divide Nodes Into the Maximum Number of Groups LeetCode Solution with the best time and space complexity. The solution to Divide Nodes Into the Maximum Number of Groups problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Divide Nodes Into the Maximum Number of Groups solution in C++
Divide Nodes Into the Maximum Number of Groups solution in Java
Divide Nodes Into the Maximum Number of Groups solution in Python
Additional Resources

2493. Divide Nodes Into the Maximum Number of Groups LeetCode Solution image

Problem Statement of Divide Nodes Into the Maximum Number of Groups

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.

Complexity Analysis

Time Complexity: O(n\log^* n)
Space Complexity: O(n)

2493. Divide Nodes Into the Maximum Number of Groups LeetCode Solution in C++

class UnionFind {
 public:
  UnionFind(int n) : id(n), rank(n) {
    iota(id.begin(), id.end(), 0);
  }

  void unionByRank(int u, int v) {
    const int i = find(u);
    const int j = find(v);
    if (i == j)
      return;
    if (rank[i] < rank[j]) {
      id[i] = j;
    } else if (rank[i] > rank[j]) {
      id[j] = i;
    } else {
      id[i] = j;
      ++rank[j];
    }
  }

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  vector<int> id;
  vector<int> rank;
};

class Solution {
 public:
  int magnificentSets(int n, vector<vector<int>>& edges) {
    vector<vector<int>> graph(n);
    UnionFind uf(n);
    unordered_map<int, int> rootToGroupSize;

    for (const vector<int>& edge : edges) {
      const int u = edge[0] - 1;
      const int v = edge[1] - 1;
      graph[u].push_back(v);
      graph[v].push_back(u);
      uf.unionByRank(u, v);
    }

    for (int i = 0; i < n; ++i) {
      const int newGroupSize = bfs(graph, i);
      if (newGroupSize == -1)
        return -1;
      const int root = uf.find(i);
      auto& groupSize = rootToGroupSize[root];
      groupSize = max(groupSize, newGroupSize);
    }

    int ans = 0;
    for (const auto& [_, groupSize] : rootToGroupSize)
      ans += groupSize;

    return ans;
  }

 private:
  int bfs(const vector<vector<int>>& graph, int u) {
    int step = 0;
    queue<int> q{{u}};
    unordered_map<int, int> nodeToStep{{u, 1}};

    while (!q.empty()) {
      ++step;
      for (int sz = q.size(); sz > 0; --sz) {
        const int u = q.front();
        q.pop();
        for (const int v : graph[u]) {
          if (!nodeToStep.contains(v)) {
            q.push(v);
            nodeToStep[v] = step + 1;
          } else if (nodeToStep[v] == step) {
            // There is an odd number of edges in the cycle.
            return -1;
          }
        }
      }
    }

    return step;
  }
};
/* code provided by PROGIEZ */

2493. Divide Nodes Into the Maximum Number of Groups LeetCode Solution in Java

N/A
// code provided by PROGIEZ

2493. Divide Nodes Into the Maximum Number of Groups LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents