3378. Count Connected Components in LCM Graph LeetCode Solution

In this guide, you will get 3378. Count Connected Components in LCM Graph LeetCode Solution with the best time and space complexity. The solution to Count Connected Components in LCM Graph 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
Complexity Analysis
Count Connected Components in LCM Graph solution in C++
Count Connected Components in LCM Graph solution in Java
Count Connected Components in LCM Graph solution in Python
Additional Resources

3378. Count Connected Components in LCM Graph LeetCode Solution image

Problem Statement of Count Connected Components in LCM Graph

You are given an array of integers nums of size n and a positive integer threshold.
There is a graph consisting of n nodes with the ith node having 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 in which 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.

Example 1:

Input: nums = [2,4,8,3,9], threshold = 5
Output: 4
Explanation:

The four connected components are (2, 4), (3), (8), (9).

Example 2:

Input: nums = [2,4,8,3,9,12], threshold = 10
Output: 2
Explanation:

The two connected components are (2, 3, 4, 8, 9), and (12).

Complexity Analysis

Time Complexity: O(n\log^* n \cdot \texttt{threshold}))
Space Complexity: O(\texttt{threshold})

3378. Count Connected Components in LCM Graph LeetCode Solution in C++

class UnionFind {
 public:
  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) {
    if (!id.contains(u))
      id[u] = u;
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  unordered_map<int, int> id;
  unordered_map<int, int> rank;
};

class Solution {
 public:
  int countComponents(vector<int>& nums, int threshold) {
    UnionFind uf;

    for (const int num : nums)
      for (int multiple = 2 * num; multiple <= threshold; multiple += num)
        uf.unionByRank(num, multiple);

    unordered_set<int> components;
    for (const int num : nums)
      components.insert(uf.find(num));
    return components.size();
  }
};
/* code provided by PROGIEZ */

3378. Count Connected Components in LCM Graph LeetCode Solution in Java

class UnionFind {
  public void unionByRank(int u, int v) {
    final int i = find(u);
    final int j = find(v);
    if (i == j)
      return;
    if (rank.get(i) < rank.get(j)) {
      id.put(i, j);
    } else if (rank.get(i) > rank.get(j)) {
      id.put(j, i);
    } else {
      id.put(i, j);
      rank.merge(j, 1, Integer::sum);
    }
  }

  public int find(int u) {
    if (!id.containsKey(u)) {
      id.put(u, u);
      rank.put(u, 0);
    }
    if (id.get(u) != u)
      id.put(u, find(id.get(u)));
    return id.get(u);
  }

  private Map<Integer, Integer> id = new HashMap<>();
  private Map<Integer, Integer> rank = new HashMap<>();
}

class Solution {
  public int countComponents(int[] nums, int threshold) {
    UnionFind uf = new UnionFind();

    for (final int num : nums)
      for (int multiple = 2 * num; multiple <= threshold; multiple += num)
        uf.unionByRank(num, multiple);

    return Arrays.stream(nums).map(uf::find).boxed().collect(Collectors.toSet()).size();
  }
}
// code provided by PROGIEZ

3378. Count Connected Components in LCM Graph LeetCode Solution in Python

class UnionFind:
  def __init__(self):
    self.id = {}
    self.rank = collections.Counter()

  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 u not in self.id:
      self.id[u] = u
    if self.id[u] != u:
      self.id[u] = self.find(self.id[u])
    return self.id[u]


class Solution:
  def countComponents(self, nums: list[int], threshold: int) -> int:
    uf = UnionFind()

    for num in nums:
      for multiple in range(2 * num, threshold + 1, num):
        uf.unionByRank(num, multiple)

    return len(set(uf.find(num) for num in nums))
 # code by PROGIEZ