952. Largest Component Size by Common Factor

Description

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.

 

Solutions

Solution: Union Find

• Time complexity: O(n * Max(Sqrt(nums)))
• Space complexity: O(Max(nums))

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const largestComponentSize = function (nums) {
  const maxNum = Math.max(...nums);
  const groups = new Array(maxNum + 1)
    .fill('')
    .map((_, index) => index);

  const unionFind = value => {
    return groups[value] === value ? value : unionFind(groups[value]);
  };

  for (const num of nums) {
    const sqrt = Math.floor(Math.sqrt(num));

    for (let value = sqrt; value > 1; value--) {
      if (num % value) continue;
      const groupA = unionFind(value);
      const groupB = unionFind(num);
      const groupC = unionFind(num / value);

      groups[groupB] = groupA;
      groups[groupC] = groupA;
    }
  }
  const countMap = new Map();
  let result = 0;

  for (const num of nums) {
    const group = unionFind(num);
    const count = countMap.get(group) ?? 0;

    countMap.set(group, count + 1);
    result = Math.max(count + 1, result);
  }
  return result;
};