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

Problem Description

Explanation

To solve this problem, we can iterate through each connected component of the graph using Depth First Search (DFS). For each connected component, we can assign alternating groups to the nodes such that adjacent nodes have group indices differing by 1. If at any point we encounter a conflict where we cannot assign groups satisfying the given conditions, we return -1. Otherwise, we return the maximum number of groups used across all connected components.

Time complexity: O(V + E), where V is the number of nodes and E is the number of edges. Space complexity: O(V) for storing the groups information.

Solutions

class Solution {
    public int maxNumOfSubgroups(int n, int[][] edges) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
            graph.get(edge[1]).add(edge[0]);
        }

        int[] groups = new int[n + 1];
        Arrays.fill(groups, -1);

        for (int i = 1; i <= n; i++) {
            if (groups[i] == -1 && !dfs(i, 0, graph, groups)) {
                return -1;
            }
        }

        int maxGroups = Arrays.stream(groups).max().getAsInt();
        return maxGroups == -1 ? -1 : maxGroups + 1;
    }

    private boolean dfs(int node, int group, List<List<Integer>> graph, int[] groups) {
        if (groups[node] != -1) {
            return groups[node] == group;
        }
        groups[node] = group;

        for (int neighbor : graph.get(node)) {
            if (!dfs(neighbor, group ^ 1, graph, groups)) {
                return false;
            }
        }
        return true;
    }
}

Problem Description

Explanation

Solutions

Related LeetCode Problems