952. Largest Component Size by Common Factor LeetCode Solution
In this guide, you will get 952. Largest Component Size by Common Factor LeetCode Solution with the best time and space complexity. The solution to Largest Component Size by Common Factor 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 of Largest Component Size by Common Factor
You are given an integer array of unique positive integers nums. Consider the following graph:
There are nums.length nodes, labeled nums[0] to nums[nums.length – 1],
There is an undirected edge between nums[i] and nums[j] if nums[i] and nums[j] share a common factor greater than 1.
Return the size of the largest connected component in the graph.
Example 1:
Input: nums = [4,6,15,35]
Output: 4
Example 2:
Input: nums = [20,50,9,63]
Output: 2
Example 3:
Input: nums = [2,3,6,7,4,12,21,39]
Output: 8
Constraints:
1 <= nums.length <= 2 * 104
1 <= nums[i] <= 105
All the values of nums are unique.
Complexity Analysis
Time Complexity:
Space Complexity:
952. Largest Component Size by Common Factor 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 largestComponentSize(vector<int>& nums) {
const int n = ranges::max(nums);
int ans = 0;
UnionFind uf(n + 1);
unordered_map<int, int> count;
for (const int num : nums)
for (int x = 2; x <= sqrt(num); ++x)
if (num % x == 0) {
uf.unionByRank(num, x);
uf.unionByRank(num, num / x);
}
for (const int num : nums)
ans = max(ans, ++count[uf.find(num)]);
return ans;
}
}; /* code provided by PROGIEZ */
952. Largest Component Size by Common Factor LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public void unionByRank(int u, int v) {
final int i = find(u);
final 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];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
private int[] id;
private int[] rank;
}
class Solution {
public int largestComponentSize(int[] nums) {
final int n = Arrays.stream(nums).max().getAsInt();
int ans = 0;
UnionFind uf = new UnionFind(n + 1);
Map<Integer, Integer> count = new HashMap<>();
for (final int num : nums)
for (int x = 2; x <= (int) Math.sqrt(num); ++x)
if (num % x == 0) {
uf.unionByRank(num, x);
uf.unionByRank(num, num / x);
}
for (final int num : nums)
ans = Math.max(ans, count.merge(uf.find(num), 1, Integer::sum));
return ans;
}
} // code provided by PROGIEZ
952. Largest Component Size by Common Factor LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
def unionByRank(self, u: int, v: int) -> None:
i = self.find(u)
j = self.find(v)
if i == j:
return
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
class Solution:
def largestComponentSize(self, nums: list[int]) -> int:
ans = 0
uf = UnionFind(max(nums) + 1)
count = collections.Counter()
for num in nums:
for x in range(2, math.isqrt(num) + 1):
if num % x == 0:
uf.unionByRank(num, x)
uf.unionByRank(num, num // x)
for num in nums:
numRoot = uf.find(num)
count[numRoot] += 1
ans = max(ans, count[numRoot])
return ans # code by PROGIEZ
