952. Largest Component Size by Common Factor

HardUnion FindArrayHash TableMathNumber Theory
Leetcode Link

Problem Description

In this problem, we are given an array nums containing unique positive integers which represents nodes in a graph. The task is to build a graph where each node is connected to another if they share a common factor greater than 1. The goal is to find the size of the largest connected component in this graph.

A connected component in an undirected graph is a subgraph where any two vertices are connected to each other by paths. We need to consider all nodes in each component to find the largest component size.

Intuition

The key to solving this problem lies in the use of a data structure known as Union-Find or Disjoint Set Union (DSU). This data structure keeps track of elements that are split into one or more disjoint sets and provides two primary operations:

  1. Find: Determine which set a particular element is in. This can be used for determining if two elements are in the same set.
  2. Union: Join two sets together.

The intuition behind using Union-Find is to group the numbers into connected components based on their common factors. Once all numbers are processed to find and union their factors, we count the size of each set using a Counter to identify the largest component.

To elaborate, we follow these steps:

  • Initialize UnionFind for all numbers up to the maximum value in nums.
  • For each number in nums, we find all the factors and the number itself, then union the number with its factors to ensure they are in the same set.
  • Once all unions are performed, we use the UnionFind to find the parent of each number (the representative element of the set). The frequency of each parent corresponds to the size of the connected component.
  • Lastly, we return the maximum size from the Counter, which indicates the largest connected component.

Solution Approach

The solution utilizes the Union-Find data structure, which is ideal for keeping track of which elements belong to the same set or connected component, especially for grouping nodes by common factors in this particular problem.

Here is a step-by-step explanation of the implementation of the Union-Find data structure and how it is used to solve the problem:

Union-Find Class

  1. UnionFind.__init__(self, n):

    • This constructor initializes the UnionFind object with n elements. Each element is its own parent at the beginning, which is why we initiate the parent list self.p with range(n), indicating that each element is the parent of itself.
  2. UnionFind.union(self, a, b):

    • This method takes two elements, a and b, and performs the union operation. It finds the parents of both a and b and, if they are from different sets (have different parents), it makes one's parent the parent of the other, effectively connecting the two elements into a single set.
  3. UnionFind.find(self, x):

    • This method finds the representative or parent of the set that element x belongs to. It uses path compression by making every node on the path from x to its root parent point directly to the root parent. This flattens the structure of the tree, leading to very short trees and, therefore, faster find operations.

Solution Class

  1. Solution.largestComponentSize(self, nums):
    • An instance of the UnionFind class is created with size max(nums) + 1 to accommodate all possible values in nums.
    • We iterate over each number v in nums, and for each number, we find its factors. This is done through iteration from 2 to sqrt(v).
    • If v % i == 0, i is a factor, and we perform the union of v with i and also with v // i to ensure all numbers that have a common factor are in the same set.
    • The while loop finds factors up to the square root of v because a number larger than sqrt(v) cannot be a factor of v without being paired with a smaller factor that has already been checked.
    • After union operations have been completed for all numbers, we iterate through the numbers again, using a Counter to count the parent (root) of each number's set.
    • The Counter object now has the size of the set for each parent, and we return the largest value from the Counter, which is the size of the largest connected component in the graph.

The overall time complexity of the algorithm is driven by the time it takes to find factors for all numbers and the union-find operations. While union-find operations are very efficient, factoring numbers can take longer, but since we're only going up to the square root, it significantly reduces the number of operations needed.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's illustrate the solution approach using a small example.

Consider the input array of unique positive integers nums = [6, 8, 3, 4].

  1. Initialize the Union-Find object for all numbers up to the maximum in nums, which is 8 in our case. So, we instantiate UnionFind class with 9 elements because we include 0.

  2. Start iterating over each number in nums and find their factors.

    • For 6:

      • The factors are 2 and 3 (ignoring 1 and 6 because 1 does not count and 6 will union with itself).
      • Perform UnionFind.union(6, 2) and UnionFind.union(6, 3).
    • For 8:

      • The factors are 2 and 4.
      • Perform UnionFind.union(8, 2) and UnionFind.union(8, 4).
    • For 3:

      • 3 is a prime number, so it only unions with itself.
      • This step has already been handled when dealing with 6.
    • For 4:

      • The factors are 2.
      • Perform UnionFind.union(4, 2).
      • Note: The factor 4 unions with itself implicitly.
  3. After all union operations, the Union-Find structure should have merged nodes 2, 4, 6, and 8 into one set, and 3 into another, since 2, 4, 6, and 8 share a common factor 2.

  4. We now iterate through the number 6, 8, 3, 4 and find the parent for each using UnionFind.find. Let's assume that 2 becomes the representative parent for its set, while 3 remains for its own set.

  5. Use a Counter to count each parent found in step 4. The counts might look like this:

1Counter({
2    "2": 4, // Since numbers 6, 8, 3, 4 are all connected through a common factor of 2
3    "3": 1  // Only number 3 is in this set, as it does not share a factor greater than 1 with the others
4})
  1. The size of the largest component is the maximum value in the Counter (the 4 associated with parent 2), which correctly suggests that there is one component containing the numbers 6, 8, 4, and another containing just 3.

Thus, using this approach, we've found that the size of the largest connected component in the graph represented by nums is 4.

Python Solution

1from collections import Counter
2
3class UnionFind:
4    def __init__(self, size):
5        # Constructor initializes an array 'parent' where each node is its own parent
6        self.parent = list(range(size))
7
8    def union(self, a, b):
9        # Merge the sets that contain a and b
10        parent_a = self.find(a)
11        parent_b = self.find(b)
12        if parent_a != parent_b:
13            self.parent[parent_a] = parent_b
14
15    def find(self, x):
16        # Find the representative (parent) of the set that contains x
17        if self.parent[x] != x:
18            # Path compression: direct attachment of x to its root
19            self.parent[x] = self.find(self.parent[x])
20        return self.parent[x]
21
22class Solution:
23    def largestComponentSize(self, nums):
24        # Given a list of numbers, we find the largest component size
25      
26        # Initializing UnionFind with the maximum possible value plus one
27        # This is to use the indexes as representatives of each number
28        uf = UnionFind(max(nums) + 1)
29      
30        # For each number, find all possible factors and perform unions
31        for value in nums:
32            # Starting from the smallest possible factor
33            factor = 2
34            while factor <= value // factor:
35                # If it's a factor, union the number and its factor as well as the complementary factor
36                if value % factor == 0:
37                    uf.union(value, factor)
38                    uf.union(value, value // factor)
39                factor += 1
40      
41        # Using a Counter to count the occurrences of each component's root in nums
42        # Find the parent of each number and calculate the most common one
43        component_sizes = Counter(uf.find(v) for v in nums)
44        return max(component_sizes.values())  # Return the size of the largest component
45

Java Solution

1class UnionFind {
2    int[] parent;
3
4    // Constructor initializes the Union-Find structure.
5    UnionFind(int size) {
6        parent = new int[size];
7        for (int i = 0; i < size; ++i) {
8            parent[i] = i; // Initially, each element is its own parent.
9        }
10    }
11
12    // Union method to combine two sets.
13    void union(int a, int b) {
14        int rootA = find(a);
15        int rootB = find(b);
16        if (rootA != rootB) {
17            parent[rootA] = rootB; // Merge the sets by updating the parent.
18        }
19    }
20
21    // Find method with path compression.
22    int find(int x) {
23        if (parent[x] != x) {
24            parent[x] = find(parent[x]); // Path compression step.
25        }
26        return parent[x]; // Return the root of the set containing 'x'.
27    }
28}
29
30class Solution {
31    // Method to find the size of the largest component in the array.
32    public int largestComponentSize(int[] nums) {
33        int maxElement = 0;
34        // Find the maximum value in the array to determine the Union-Find size.
35        for (int num : nums) {
36            maxElement = Math.max(maxElement, num);
37        }
38        UnionFind unionFind = new UnionFind(maxElement + 1);
39
40        // Connect components based on common factors.
41        for (int num : nums) {
42            for (int factor = 2; factor <= Math.sqrt(num); ++factor) {
43                if (num % factor == 0) {
44                    unionFind.union(num, factor); // Union by a factor.
45                    unionFind.union(num, num / factor); // Union by complementary factor.
46                }
47            }
48        }
49
50        // Count the frequency of each representative.
51        int[] count = new int[maxElement + 1];
52        int largestComponentSize = 0;
53        for (int num : nums) {
54            int root = unionFind.find(num);
55            count[root]++;
56            largestComponentSize = Math.max(largestComponentSize, count[root]); // Update the largest component size.
57        }
58        return largestComponentSize;
59    }
60}
61

C++ Solution

1#include <vector>
2#include <numeric>
3#include <algorithm>
4using namespace std;
5
6// UnionFind is a data structure that keeps track of disjoint sets for union-find operations.
7class UnionFind {
8public:
9    // 'parents' holds the representative (or parent) for each element in the set.
10    vector<int> parents;
11
12    // Constructor initializes a UnionFind object of size 'size'.
13    UnionFind(int size)
14        : parents(size) {
15        // Fill 'parents' with elements from 0 to size-1. Each element is its own parent initially.
16        iota(parents.begin(), parents.end(), 0);
17    }
18
19    // 'unite' merges the sets that contain elements 'a' and 'b'.
20    void unite(int a, int b) {
21        // Find the parents of 'a' and 'b'.
22        int parentA = find(a), parentB = find(b);
23        // If they have different parents, make one the parent of the other (union by rank or size not considered here).
24        if (parentA != parentB) parents[parentA] = parentB;
25    }
26
27    // 'find' returns the representative of the set that contains 'x', implementing path compression.
28    int find(int x) {
29        // If 'x' is not its own parent, recursively find the parent and do path compression.
30        if (parents[x] != x) parents[x] = find(parents[x]);
31        return parents[x];
32    }
33};
34
35class Solution {
36public:
37    // 'largestComponentSize' finds and returns the size of the largest connected component in the graph constructed from 'nums'.
38    int largestComponentSize(vector<int>& nums) {
39        // Get the maximum value in 'nums' to set the size of UnionFind.
40        int maxNum = *max_element(nums.begin(), nums.end());
41        UnionFind uf(maxNum + 1);
42
43        // Loop over each number and unite it with its factors
44        // to build a graph where each node is connected to its factors.
45        for (int num : nums) {
46            for (int factor = 2; factor <= sqrt(num); ++factor) {
47                if (num % factor == 0) {
48                    uf.unite(num, factor);
49                    uf.unite(num, num / factor);
50                }
51            }
52        }
53
54        // 'counts' holds the size (number of elements) for each set.
55        vector<int> counts(maxNum + 1, 0);
56        int largestSize = 0; // Will hold the largest component size.
57
58        // Iterate over 'nums' to find the size of the component/set
59        // each number belongs to by finding its parent.
60        for (int num : nums) {
61            int root = uf.find(num);
62            ++counts[root]; // Increase the count for this root.
63            largestSize = max(largestSize, counts[root]); // Update 'largestSize' if needed.
64        }
65      
66        // Return the size of the largest component.
67        return largestSize;
68    }
69};
70

Typescript Solution

1// The UnionFind class is not defined since global variables and methods are used instead.
2
3// The 'parents' array holds the representative (or parent) for each element in the set.
4let parents: number[] = [];
5
6// Function to initialize the UnionFind with a specified size.
7function initializeUnionFind(size: number): void {
8    parents = Array.from({ length: size }, (_, index) => index);
9}
10
11// 'unite' merges the sets that contain elements 'a' and 'b'.
12function unite(a: number, b: number): void {
13    const parentA = find(a), parentB = find(b);
14    if (parentA != parentB) parents[parentA] = parentB;
15}
16
17// 'find' returns the representative of the set that contains 'x', implementing path compression.
18function find(x: number): number {
19    if (parents[x] !== x) parents[x] = find(parents[x]);
20    return parents[x];
21}
22
23// 'largestComponentSize' finds and returns the size of the largest connected component 
24// in the graph constructed from 'nums'.
25function largestComponentSize(nums: number[]): number {
26    const maxNum = Math.max(...nums);
27    initializeUnionFind(maxNum + 1);
28
29    for (const num of nums) {
30        for (let factor = 2; factor <= Math.sqrt(num); ++factor) {
31            if (num % factor === 0) {
32                unite(num, factor);
33                unite(num, num / factor);
34            }
35        }
36    }
37
38    const counts = new Array(maxNum + 1).fill(0);
39    let largestSize = 0;
40
41    for (const num of nums) {
42        const root = find(num);
43        counts[root]++;
44        largestSize = Math.max(largestSize, counts[root]);
45    }
46
47    return largestSize;
48}
49
50// Example of usage:
51// const nums = [4, 6, 15, 35];
52// console.log(largestComponentSize(nums)); // Output the size of the largest component.
53

Time and Space Complexity

The given code is a solution for finding the largest connected component size where each element is connected if they share a common factor greater than 1. The code implements a UnionFind class for disjoint sets and uses it to union elements with common factors. Let's analyze its time and space complexity:

Time Complexity

The time complexity components include:

  1. Initialization of UnionFind class: The constructor initializes the parents' list with n elements. This takes O(n) time where n is the maximum number in the nums array.

  2. Union-Find Operations (union and find): Each union and find operation takes near constant time because of path compression in the find method. Without considering the overhead of finding factors, the complexity in a practical case is O(α(n)), where α is the inverse Ackermann function, which grows extremely slowly and is <= 4 for practically all conceivable problem sizes.

  3. Factorization Process: The loop finds factors of each v in nums effectively implementing trial division. For each v, the loop runs O(sqrt(v)) times in the worst case. Summing over all v in nums, the total time would be O(sum(sqrt(v) for v in nums)).

  4. Building the counter to find the maximum component size takes O(k), where k is the number of unique parents, which is less than O(n).

Combining the above, and considering that finding factors dominates the complexity, the total worst-case time complexity is approximately O(n + kα(n) + sum(sqrt(v) for v in nums)). However, because finding factors with trial division is the most expensive operation and is called multiple times, this simplifies to O(sum(sqrt(v) for v in nums)) when comparing large numbers with large prime factors.

Space Complexity

The space complexity is composed of:

  1. The UnionFind data structure which maintains an array of size n. This is O(n).

  2. The counter created at the end of the function to find the maximum component size requires space proportional to the number of unique elements in nums, which is O(k), where k is the length of nums.

The total space complexity is O(n + k), which simplifies to O(n) as n (the maximum number in nums) is the dominant term.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫