952

952. Largest Component Size by Common Factor (Hard)

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.

Companies:
Google

Related Topics:
Array, Math, Union Find

Solution 1. Union Find + Factorization

1. Factorize each numbers in A, and group the numbers by factors.
2. Use UnionFind to union the numbers in the same group
3. Return the size of the largest union.

• Step 1 takes O(N * sqrt(M)) time (factorizing a number takes O(sqrt(M)) time) and O(N * sqrt(M)) space where M is the maximum number in A.
• Step 2 takes O(N * sqrt(M)) time (in the worst case, sqrt(M) factors/groups and each group has N elements) and O(N) space (due to UnionFind).
• Step 3 takes O(N) time and O(1) space.

So overall this solution takes O(N * sqrt(M)) time and O(N * sqrt(M)) space.

// OJ: https://leetcode.com/problems/largest-component-size-by-common-factor/
// Author: github.com/lzl124631x
// Time: O(N * sqrt(M)) where `N` is the length of `A`, and `M` is the maximum number in `A`.
// Space: O(N * sqrt(M))
class UnionFind {
    vector<int> id, size;
public:
    UnionFind(int N) : id(N), size(N, 1) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        int p = find(a), q = find(b);
        if (p == q) return;
        id[p] = q;
        size[q] += size[p];
    }
    int getSize(int a) { return size[find(a)]; }
};
class Solution {
    vector<int> factors(int n) {
        vector<int> ans;
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) ans.push_back(i);
            while (n % i == 0) n /= i;
        }
        if (n > 1) ans.push_back(n);
        return ans;
    }
public:
    int largestComponentSize(vector<int>& A) {
        int N = A.size(), ans = 0;
        UnionFind uf(N);
        unordered_map<int, vector<int>> m; // prime factor -> all indexes of numbers with this factor
        for (int i = 0; i < N; ++i) {
            for (int &f : factors(A[i])) m[f].push_back(i);
        }
        for (auto &[f, indices] : m) {
            for (int i = 1; i < indices.size(); ++i) uf.connect(indices[0], indices[i]);
        }
        for (int i = 0; i < N; ++i) ans = max(ans, uf.getSize(i));
        return ans;
    }
};

Or we can merge step 1 and step 2 together by only storing a representative number for each factor in the map. For all subsequent numbers with the same factor, we just need to union it with the representative number. In this way, reduce the space complexity from O(N * sqrt(M)) to O(N + sqrt(M)).

// OJ: https://leetcode.com/problems/largest-component-size-by-common-factor/
// Author: github.com/lzl124631x
// Time: O(N * sqrt(M))
// Space: O(N + sqrt(M))
class UnionFind {
    vector<int> id, size;
public:
    UnionFind(int N) : id(N), size(N, 1) {
        iota(begin(id), end(id), 0);
    }
    int find(int a) {
        return id[a] == a ? a : (id[a] = find(id[a]));
    }
    void connect(int a, int b) {
        int p = find(a), q = find(b);
        if (p == q) return;
        id[p] = q;
        size[q] += size[p];
    }
    int getSize(int a) { return size[find(a)]; }
};
class Solution {
    vector<int> factors(int n) {
        vector<int> ans;
        for (int i = 2; i * i <= n; ++i) {
            if (n % i == 0) ans.push_back(i);
            while (n % i == 0) n /= i;
        }
        if (n > 1) ans.push_back(n);
        return ans;
    }
public:
    int largestComponentSize(vector<int>& A) {
        int N = A.size(), ans = 0;
        UnionFind uf(N);
        unordered_map<int, int> m;  // primce factor -> a representative (the first) number with this factor
        for (int i = 0; i < N; ++i) {
            for (int &f : factors(A[i])) { 
                if (m.count(f)) uf.connect(i, m[f]);
                else m[f] = i;
            }
        }
        for (int i = 0; i < N; ++i) ans = max(ans, uf.getSize(i));
        return ans;
    }
};