LeetCode 952: Largest Component Size by Common Factor Solution

Master LeetCode problem 952 (Largest Component Size by Common Factor), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

952. Largest Component Size by Common Factor

Hard

Array Hash Table Math Union Find Number Theory

Problem Explanation

Explanation

To solve this problem, we need to first find the common factors of each number in the input array nums. Then, we can create a graph where each node represents a number in nums, and there is an edge between two nodes if their corresponding numbers share a common factor greater than 1.

Next, we perform a depth-first search (DFS) to find the size of the largest connected component in the graph. We keep track of the size of each component using a hashmap. Finally, we return the size of the largest connected component.

Algorithm:
1. Create a hashmap parent to store the parent of each number in the input array.
2. Create a hashmap size to store the size of each component.
3. Create a function find to find the parent of a number in the input array.
4. Create a function union to union two components by updating their parent pointers.
5. Iterate over each number in the input array nums:
  - For each number num, find its factors and iterate over them:
    - If the factor exists in the parent hashmap, union the current number num and the factor.
6. Iterate over each number in the input array nums:
  - Find the parent of the number using the find function.
  - Update the size of the component in the size hashmap.
7. Find the largest size in the size hashmap and return it.
Time Complexity: The time complexity of this algorithm is O(n√m * α(n)), where n is the number of elements in the input array nums, and m is the maximum value in nums. α(n) is the inverse Ackermann function, which is very slow-growing and can be considered as constant for practical purposes.
Space Complexity: The space complexity is O(n) where n is the number of elements in the input array nums.

Solution Code

class Solution {
    public int largestComponentSize(int[] nums) {
        Map<Integer, Integer> parent = new HashMap<>();
        Map<Integer, Integer> size = new HashMap<>();
        
        for (int num : nums) {
            for (int i = 2; i * i <= num; i++) {
                if (num % i == 0) {
                    union(parent, size, num, i);
                    union(parent, size, num, num / i);
                }
            }
            union(parent, size, num, num);
        }
        
        int max = 0;
        for (int num : nums) {
            int p = find(parent, num);
            size.put(p, size.getOrDefault(p, 0) + 1);
            max = Math.max(max, size.get(p));
        }
        
        return max;
    }
    
    private void union(Map<Integer, Integer> parent, Map<Integer, Integer> size, int x, int y) {
        int px = find(parent, x);
        int py = find(parent, y);
        if (px != py) {
            parent.put(px, py);
            size.put(py, size.getOrDefault(py, 0) + size.getOrDefault(px, 0));
        }
    }
    
    private int find(Map<Integer, Integer> parent, int x) {
        parent.putIfAbsent(x, x);
        if (parent.get(x) != x) {
            parent.put(x, find(parent, parent.get(x)));
        }
        return parent.get(x);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 952 (Largest Component Size by Common Factor)?

This page provides optimized solutions for LeetCode problem 952 (Largest Component Size by Common Factor) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 952 (Largest Component Size by Common Factor)?

The time complexity for LeetCode 952 (Largest Component Size by Common Factor) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 952 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 952 in Java, C++, or Python.

Back to LeetCode Solutions