LeetCode Solutions

952. Largest Component Size by Common Factor

Time:

Space:

			

class UnionFind {
 public:
  UnionFind(int n) : id(n + 1) {
    iota(begin(id), end(id), 0);
  }

  void union_(int u, int v) {
    id[find(u)] = find(v);
  }

  int find(int u) {
    return id[u] == u ? u : id[u] = find(id[u]);
  }

 private:
  vector<int> id;
};

class Solution {
 public:
  int largestComponentSize(vector<int>& A) {
    const int n = *max_element(begin(A), end(A));
    int ans = 0;
    UnionFind uf(n);
    unordered_map<int, int> count;

    for (const int a : A)
      for (int num = 2; num <= sqrt(a); ++num)
        if (a % num == 0) {
          uf.union_(a, num);
          uf.union_(a, a / num);
        }

    for (const int a : A)
      ans = max(ans, ++count[uf.find(a)]);

    return ans;
  }
};

			

class UnionFind {
  public UnionFind(int n) {
    id = new int[n + 1];
    for (int i = 0; i < id.length; ++i)
      id[i] = i;
  }

  public void union(int u, int v) {
    id[find(u)] = find(v);
  }

  public int find(int u) {
    return id[u] == u ? u : (id[u] = find(id[u]));
  }

  private int[] id;
}

class Solution {
  public int largestComponentSize(int[] A) {
    final int n = Arrays.stream(A).max().getAsInt();
    int ans = 0;
    UnionFind uf = new UnionFind(n);
    Map<Integer, Integer> count = new HashMap<>();

    for (int a : A)
      for (int num = 2; num <= (int) Math.sqrt(a); ++num)
        if (a % num == 0) {
          uf.union(a, num);
          uf.union(a, a / num);
        }

    for (int a : A) {
      int pa = uf.find(a);
      count.put(pa, count.getOrDefault(pa, 0) + 1);
      ans = Math.max(ans, count.get(pa));
    }

    return ans;
  }
}

			

class UnionFind:
  def __init__(self, n: int):
    self.id = [i for i in range(n + 1)]

  def union(self, u: int, v: int) -> bool:
    i = self.find(u)
    j = self.find(v)
    if i == j:
      return False
    self.id[i] = j
    return True

  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, A: List[int]) -> int:
    ans = 0
    uf = UnionFind(max(A))
    count = Counter()

    for a in A:
      for num in range(2, int(sqrt(a) + 1)):
        if a % num == 0:
          uf.union(a, num)
          uf.union(a, a // num)

    for a in A:
      pa = uf.find(a)
      count[pa] += 1
      ans = max(ans, count[pa])

    return ans