Largest Component Size by Common Factor

Description

Given a non-empty array of unique positive integers A, consider the following graph:

• There are A.length nodes, labelled A[0] to A[A.length - 1];
• There is an edge between A[i] and A[j] if and only if A[i] and A[j] share a common factor greater than 1.

Return the size of the largest connected component in the graph.

 

Example 1:

Input: [4,6,15,35]
Output: 4

Example 2:

Input: [20,50,9,63]
Output: 2

Example 3:

Input: [2,3,6,7,4,12,21,39]
Output: 8

Note:

1. 1 <= A.length <= 20000
2. 1 <= A[i] <= 100000

Solution(javascript)

/*
 * @lc app=leetcode id=952 lang=javascript
 *
 * [952] Largest Component Size by Common Factor
 */

// @lc code=start

// const gcd = (x, y) => {
//   if (x > y) {
//     return gcd(y, x)
//   }
//   if (x === 0) {
//     return y
//   }
//   if (y === 0) {
//     return x
//   }
//   return gcd(y % x, x)
// }

class UnionFind {
  constructor(n) {
    this.parent = new Array(n).fill(0).map((val, index) => index)
    this.size = new Array(n).fill(1)
    this.count = n
  }

  root(i) {
    while (this.parent[i] !== undefined && i !== this.parent[i]) {
      this.parent[i] = this.parent[this.parent[i]] // Path compression
      i = this.parent[i]
    }
    return i
  }

  connected(a, b) {
    return this.root(a) === this.root(b)
  }

  union(a, b) {
    const rootA = this.root(a)
    const rootB = this.root(b)
    if (rootA === rootB) {
      return
    }
    if (this.parent[rootA] < this.parent[rootB]) {
      this.parent[rootA] = rootB
      this.size[rootB] += this.size[rootA]
    } else {
      this.parent[rootB] = rootA
      this.size[rootA] += this.size[rootB]
    }
    this.count -= 1
  }

  getCount() {
    return this.count
  }
}

// /** Time Limit Exceeded
//  * @param {number[]} A
//  * @return {number}
//  */
// const largestComponentSize = function (A) {
//   A.sort((a, b) => b - a)
//   const uf = new UnionFind(A.length)
//   for (let i = 0; i < A.length; i++) {
//     for (let j = i + 1; j < A.length; j++) {
//       if (!uf.connected(i, j)) {
//         if (gcd(A[i], A[j]) > 1) {
//           uf.union(i, j)
//         }
//       }
//     }
//   }
//   return uf.size.reduce((acc, current) => Math.max(acc, current))
// }

/**
 * @param {number[]} A
 * @return {number}
 */
const largestComponentSize = function (A) {
  const uf = new UnionFind(A.length)
  const map = {}
  const unionHelper = (factor, index) => {
    if (map[factor] !== undefined) {
      uf.union(index, map[factor])
    } else {
      map[factor] = index
    }
  }
  for (let i = 0; i < A.length; i++) {
    const num = A[i]
    for (let j = 2; j * j <= num; j++) {
      if (num % j === 0) {
        unionHelper(j, i)
        unionHelper(num / j, i)
      }
    }
    unionHelper(num, i)
  }
  return uf.size.reduce((acc, a) => Math.max(acc, a))
}

// @lc code=end

// console.log(
//   largestComponentSize(
//     [2, 3, 6, 7, 4, 12, 21, 39],
//   ),
// )