LeetCode 3378: Count Connected Components in LCM Graph Solution

Master LeetCode problem 3378 (Count Connected Components in LCM Graph), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3378. Count Connected Components in LCM Graph

Hard

Array Hash Table Math Union Find Number Theory

Problem Explanation

Explanation:

To solve this problem, we can use a disjoint set union (DSU) data structure. We will iterate through all pairs of nodes in the graph and union nodes if their least common multiple (LCM) is less than or equal to the threshold. Finally, we will count the number of connected components by counting the number of unique parents in the DSU structure.

Algorithm:

Initialize a DSU structure with size n, where n is the number of nodes.
Iterate through all pairs of nodes i and j (0-indexed):
- Calculate the LCM of nums[i] and nums[j].
- If the LCM is less than or equal to the threshold, union nodes i and j in the DSU structure.
Count the number of unique parents in the DSU structure to determine the number of connected components.

Time Complexity:

The time complexity of this algorithm is O(n * sqrt(max(nums)) * log(max(nums))) where n is the number of nodes and max(nums) is the maximum value in the nums array.

Space Complexity:

The space complexity is O(n) for the DSU structure.

Solution Code

class DSU {
    int[] parent;

    public DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public void union(int x, int y) {
        parent[find(x)] = find(y);
    }
}

class Solution {
    public int countComponents(int[] nums, int threshold) {
        int n = nums.length;
        DSU dsu = new DSU(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (lcm(nums[i], nums[j]) <= threshold) {
                    dsu.union(i, j);
                }
            }
        }
        Set<Integer> components = new HashSet<>();
        for (int i = 0; i < n; i++) {
            components.add(dsu.find(i));
        }
        return components.size();
    }

    private int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3378 (Count Connected Components in LCM Graph)?

This page provides optimized solutions for LeetCode problem 3378 (Count Connected Components in LCM Graph) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3378 (Count Connected Components in LCM Graph)?

The time complexity for LeetCode 3378 (Count Connected Components in LCM Graph) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3378 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3378 in Java, C++, or Python.

Back to LeetCode Solutions