Facebook Pixel

3378. Count Connected Components in LCM Graph

HardUnion FindArrayHash TableMathNumber Theory
Leetcode Link

Problem Description

You are given an array of integers nums of size n and a positive integer threshold.

There is a graph consisting of n nodes where the i-th node has a value of nums[i]. Two nodes i and j in the graph are connected via an undirected edge if lcm(nums[i], nums[j]) <= threshold.

Return the number of connected components in this graph.

A connected component is a subgraph of a graph where there exists a path between any two vertices, and no vertex of the subgraph shares an edge with a vertex outside of the subgraph.

The term lcm(a, b) denotes the least common multiple of a and b.

Intuition

To solve this problem, consider the following steps:

  1. Understanding LCM and Connectivity: Two nodes with values a and b are connected if the least common multiple lcm(a, b) is less than or equal to the threshold. The least common multiple is a measure of the smallest number that is divisible by both a and b.

  2. Graph and Union-Find: We can model this problem as a graph problem where each element of nums is a node. Use the Union-Find (Disjoint Set Union, DSU) data structure to efficiently manage connected components. The connection between nodes is established based on the condition involving LCM.

  3. Union-Find Operations: The DSU helps in finding the root of any node and uniting two nodes if their values satisfy the LCM condition. Each number in the nums array relates to many numbers derived by multiplying it, up to the threshold (j), and this creates a union among these values.

  4. Iterate and Union: For each number, iterate through its multiples up to the threshold. Use the union operation from the DSU to connect it with its multiples.

  5. Determine Unique Components: After processing all connections, look at the unique root elements represented in the DSU structure. These roots indicate how many separate components exist.

Using this structured approach, the solution efficiently computes the number of connected components in the graph defined by the nums array and the threshold.

Learn more about Union Find and Math patterns.

Solution Approach

The solution leverages the Union-Find, also known as Disjoint Set Union (DSU), to efficiently track and manage connected components in the graph derived from the nums array and the threshold. Here’s how the solution is structured:

  1. Data Structure (DSU):

    • A DSU is initialized with each node as its own parent and a rank for efficient union operations.
    • The find operation employs path compression to make future queries faster by flattening the structure of the tree whenever find is called.
    • The union_set operation uses rank to ensure minimal tree height, optimizing the union of two sets.

  2. Iterating through nums:

    • For each element in nums, consider its multiples from itself up to the threshold.
    • Use the union_set method to connect the current number with its multiples. This links numbers in nums implicitly by their divisors and multiples according to the rules dictated by the LCM condition.

  3. Handling Unique Parents:

    • After establishing connections, iterate over the nums array to verify the root parent of each element using the find operation.
    • Elements with values exceeding the threshold are inherently disconnected from others and must be considered individually.
    • Collect the unique parents to determine the number of distinct connected components.

Here is how the DSU implementation is used in the solution:

class DSU:
    def __init__(self, n):
        self.parent = {i: i for i in range(n)}
        self.rank = {i: 0 for i in range(n)}

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union_set(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u != v:
            if self.rank[u] < self.rank[v]:
                u, v = v, u
            self.parent[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

class Solution:
    def countComponents(self, nums, threshold):
        dsu = DSU(threshold + 1)

        for num in nums:
            for j in range(num, threshold + 1, num):
                dsu.union_set(num, j)

        unique_parents = set()
        for num in nums:
            if num > threshold:
                unique_parents.add(num)
            else:
                unique_parents.add(dsu.find(num))

        return len(unique_parents)

This implementation efficiently tracks and calculates the number of connected components by ensuring each number's connectivity through its multiples, respecting the given threshold constraint.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example to understand the solution approach.

Example:

Suppose we have the array nums = [2, 3, 4, 9] and threshold = 6.

Steps:

  1. Initialize DSU:

    • We initialize a Disjoint Set Union (DSU) with each element being its own parent. Assume node indices match their values initially for simplicity.

  2. Iterate through nums:

    • Consider the element 2.
      • It connects to its multiples within the threshold: 2, 4, 6. The union operation is applied to link these.
    • Consider the element 3.
      • It connects to its multiples: 3, 6. Union operation connects them.
    • Element 4 and its multiples (up to threshold) are already processed via 2, so no additional connections are needed.
    • Element 9 is greater than the threshold, so it stands alone.

  3. Process Unions:

    • Utilize the find operation to ensure path compression within the DSU. Each node will point directly to its root parent.

  4. Determine Unique Components:

    • For each element in nums, determine its root parent.

    • Elements: 2, 3, 4 form one component through connections.

    • Element 9 forms its own component.

    • Unique root parents: {2, 3, 9}.

  5. Count Components:

    • The number of unique root parents gives the number of connected components: 3.

This simplified example illustrates how the DSU structure assists in managing connectivity efficiently while respecting the threshold constraints for LCM-based connections.

Solution Implementation

1class DSU:
2    def __init__(self, n):
3        # Initialize the parent and rank dictionaries
4        self.parent = {i: i for i in range(n)}
5        self.rank = {i: 0 for i in range(n)}
6
7    def make_set(self, v):
8        # Create a singleton set with rank 1
9        self.parent[v] = v
10        self.rank[v] = 1
11
12    def find(self, x):
13        # Find the root of the set in which element x is and apply path compression
14        if self.parent[x] != x:
15            self.parent[x] = self.find(self.parent[x])
16        return self.parent[x]
17
18    def union_set(self, u, v):
19        # Perform the union of two sets containing u and v
20        root_u = self.find(u)
21        root_v = self.find(v)
22        if root_u != root_v:
23            # Union by rank
24            if self.rank[root_u] < self.rank[root_v]:
25                root_u, root_v = root_v, root_u
26            self.parent[root_v] = root_u
27            if self.rank[root_u] == self.rank[root_v]:
28                self.rank[root_u] += 1
29
30
31class Solution:
32    def countComponents(self, nums, threshold):
33        # Create a Disjoint Set Union (DSU) object
34        dsu = DSU(threshold + 1)
35
36        # Union elements based on divisibility
37        for num in nums:
38            for j in range(num, threshold + 1, num):
39                dsu.union_set(num, j)
40
41        # Collect unique parents (unique components)
42        unique_parents = set()
43        for num in nums:
44            # For numbers beyond the threshold, they remain in their own group
45            if num > threshold:
46                unique_parents.add(num)
47            else:
48                # Find the parent of the number within the DSU
49                unique_parents.add(dsu.find(num))
50
51        # Return the count of unique components
52        return len(unique_parents)
53
1import java.util.HashMap;
2import java.util.HashSet;
3import java.util.Map;
4import java.util.Set;
5
6class DSU {
7    private Map<Integer, Integer> parent; // To store parent of each node
8    private Map<Integer, Integer> rank;   // To store rank of each node
9
10    // Constructor to initialize DSU with maximum potential node value
11    public DSU(int n) {
12        parent = new HashMap<>();
13        rank = new HashMap<>();
14        for (int i = 0; i <= n; i++) {
15            parent.put(i, i); // Set each node as its own parent (self loop)
16            rank.put(i, 0);   // Initialize rank as 0
17        }
18    }
19
20    // Function to make a set with a single element
21    public void makeSet(int v) {
22        parent.put(v, v); // Set the parent of v to itself
23        rank.put(v, 1);   // Initialize rank as 1
24    }
25
26    // Function to find the representative (parent) of the set containing x
27    public int find(int x) {
28        if (parent.get(x) != x) {
29            // Path compression: All nodes in the path directly point to the root
30            parent.put(x, find(parent.get(x)));
31        }
32        return parent.get(x);
33    }
34
35    // Function to union two sets containing u and v
36    public void unionSet(int u, int v) {
37        u = find(u);
38        v = find(v);
39      
40        // Union by rank: attach smaller tree under larger tree
41        if (u != v) {
42            if (rank.get(u) < rank.get(v)) {
43                int temp = u;
44                u = v;
45                v = temp;
46            }
47            parent.put(v, u); // Attach v to u
48          
49            // If rank of both trees are same, increase the rank of the resulting tree
50            if (rank.get(u).equals(rank.get(v))) {
51                rank.put(u, rank.get(u) + 1);
52            }
53        }
54    }
55}
56
57class Solution {
58    // Function to count unique components after unions based on a threshold
59    public int countComponents(int[] nums, int threshold) {
60        DSU dsu = new DSU(threshold);
61      
62        // For each number, union sets of all its multiples up to the threshold
63        for (int num : nums) {
64            for (int multiple = num; multiple <= threshold; multiple += num) {
65                dsu.unionSet(num, multiple);
66            }
67        }
68
69        Set<Integer> uniqueParents = new HashSet<>();
70        for (int num : nums) {
71            if (num > threshold) {
72                // If the number exceeds the threshold, consider it as a unique component
73                uniqueParents.add(num);
74            } else {
75                // Add the representative of the set containing the number
76                uniqueParents.add(dsu.find(num));
77            }
78        }
79
80        return uniqueParents.size();
81    }
82}
83
1#include <unordered_map>
2#include <unordered_set>
3#include <vector>
4using namespace std;
5
6// Disjoint Set Union (DSU) data structure
7typedef struct DSU {
8    unordered_map<int, int> parent, rank;
9  
10    // Constructor to initialize DSU with 'n' elements
11    DSU(int n) {
12        for (int i = 0; i < n; ++i) {
13            parent[i] = i;  // Each element is its own parent initially
14            rank[i] = 0;    // Rank is initialized to 0 for all elements
15        }
16    }
17
18    // Make a new set containing the single element 'v'
19    void makeSet(int v) {
20        parent[v] = v;
21        rank[v] = 1;
22    }
23
24    // Find the representative (root) of the set containing 'x'
25    int find(int x) {
26        if (parent[x] == x) {
27            return x;  // 'x' is the root of its own set
28        }
29        // Path compression optimization
30        return parent[x] = find(parent[x]);
31    }
32
33    // Union by rank for the sets containing 'u' and 'v'
34    void unionSet(int u, int v) {
35        u = find(u);  // Find root of the set containing 'u'
36        v = find(v);  // Find root of the set containing 'v'
37      
38        if (u != v) {  // If 'u' and 'v' are not already in the same set
39            // Union by rank
40            if (rank[u] < rank[v]) swap(u, v);
41            parent[v] = u;  // Make 'u' the parent of 'v'
42            if (rank[u] == rank[v]) rank[u]++;  // Increment rank if equal
43        }
44    }
45} DSU;
46
47class Solution {
48public:
49    // Function to count the number of components with respect to a threshold
50    int countComponents(vector<int>& nums, int threshold) {
51        DSU dsu(threshold + 1); // Initialize DSU with 'threshold + 1' elements
52        for (auto& num : nums) { // Iterate over each number in 'nums'
53            // Union all multiples of 'num' from 'num' to 'threshold'
54            for (int j = num; j <= threshold; j += num) {
55                dsu.unionSet(num, j); // Union 'num' with its multiple 'j'
56            }
57        }
58      
59        unordered_set<int> uniqueParents; // To store unique parent representatives
60        for (auto& num : nums) { // Iterate over each number in 'nums'
61            if (num > threshold) {
62                uniqueParents.insert(num); // If 'num' is greater than 'threshold', insert 'num'
63            } else {
64                uniqueParents.insert(dsu.find(num)); // Otherwise, insert the representative of 'num'
65            }
66        }
67        return uniqueParents.size(); // Return the size of unique parent representatives
68    }
69};
70
1// Disjoint Set Union (DSU) data structure.
2// This implementation uses a parent map and rank map to manage the sets.
3const parent: { [key: number]: number } = {};
4const rank: { [key: number]: number } = {};
5
6// Initialize DSU with `n` elements. Each element is initialized to be its own parent.
7function initializeDSU(n: number): void {
8    for (let i = 0; i < n; ++i) {
9        parent[i] = i;  // Each element is its own parent
10        rank[i] = 0;    // Initialize rank as 0
11    }
12}
13
14// Create a new set that contains the single element `v`.
15function makeSet(v: number): void {
16    parent[v] = v;
17    rank[v] = 1;
18}
19
20// Find the representative (root) of the set containing `x`.
21// Implements path compression optimization to make future queries faster.
22function find(x: number): number {
23    if (parent[x] !== x) {
24        parent[x] = find(parent[x]);  // Path compress while finding the root
25    }
26    return parent[x];
27}
28
29// Union by rank the sets containing `u` and `v`.
30function unionSet(u: number, v: number): void {
31    u = find(u);  // Find root of the set containing `u`
32    v = find(v);  // Find root of the set containing `v`
33  
34    if (u !== v) {  // Only union if `u` and `v` are in different sets
35        // Union by rank: attach smaller rank tree under root of higher rank
36        if (rank[u] < rank[v]) {
37            [u, v] = [v, u];
38        }
39        parent[v] = u;  // Attach `v` tree under `u`
40        if (rank[u] === rank[v]) rank[u]++;  // Increment rank if they were equal
41    }
42}
43
44// Count the number of components in `nums` with respect to the `threshold`.
45function countComponents(nums: number[], threshold: number): number {
46    initializeDSU(threshold + 1);  // Initialize DSU with `threshold + 1` elements
47  
48    // Iterate over each number in `nums`
49    for (const num of nums) {
50        // Union all multiples of `num` from `num` to `threshold`
51        for (let j = num; j <= threshold; j += num) {
52            unionSet(num, j);  // Union `num` with its multiple `j`
53        }
54    }
55  
56    const uniqueParents = new Set<number>();  // To store unique parent representatives
57  
58    // Iterate over each number in `nums`
59    for (const num of nums) {
60        if (num > threshold) {
61            uniqueParents.add(num);  // If `num` is greater than `threshold`, add `num` itself
62        } else {
63            uniqueParents.add(find(num));  // Otherwise, add the representative of `num`
64        }
65    }
66  
67    return uniqueParents.size;  // Return the count of unique parent representatives
68}
69

Time and Space Complexity

The code consists of defining a Disjoint Set Union (DSU) class and a method to count the number of components given a list of numbers and a threshold. We'll analyze the time and space complexity of this solution.

Time Complexity

  1. Initialization of DSU:

    • Constructing dictionaries for parent and rank takes O(n), where n is threshold + 1.

  2. Union Operations:

    • Iterating over each num in nums, and for each num, iterating over multiples up to the threshold requires examining a number of elements akin to O(n log n). In general, the union operations use approximately O(log n).

  3. Find Operations:

    • dsu.find(num) operates in nearly constant time O(α(n)) due to path compression, where α is the inverse Ackermann function.

  4. Total Loops:

    • The primary loop runs O(n) times for the union and find operations, which simplifies the asymptotic behavior to O(n log n) for practical purposes.

Overall, the time complexity is O(n log n), with n being the threshold.

Space Complexity

  1. DSU Data Structures:

    • Storing the parent and rank dictionaries implies O(n) space, where n is the number of elements up to the threshold.

  2. Unique Parents Set:

    • The space for the set unique_parents consists of at most O(k) elements where k is the length of nums.

Therefore, the space complexity is O(n) primarily dictated by the DSU storage requirements and the size of unique_parents.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Recommended Readings

DSU/Union Find Fundamentals

Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More