Largest Component Size by Common Factor | LeetCode | Solution Explained

Largest Component Size by Common Factor. I make this problem easy by explaining the solution in an intuitive manner. Problem Link.

0. Largest Component Size by Common Factor: Problem Discussion

• Given: nums, an array of numbers
• Goal: max(component_size), an integer

We define one connected component as a set of nodes connected by one or more edges. These edges have a special property. They have a common factor >1.

1. Largest Component Size by Common Factor: Bruteforce Solution (TLE)

1.0. Logic

We code the solution up as directed. Feel free to look up the following reference for DSU, as I explain it for another question in detail.

• First, we create a DSU/UF since we are talking in terms of the connected components
• DSU contains two pieces of information
  • who the representative is, for ith index
  • what the size is, for the ith index
• As you can see, at the very end, we can just return the max(dsu.sizes). Yes, its that easy.
• Now that we have the DSU, we want to add the edges. How?
• As the question states, we want to add an edge between nums[i] and nums[j] IF their common divisor/factor > 1. In other words, if their gcd is >1, we can add an edge between the two nodes.
• This also means we have two iterators, i and j, both taking O(N) to iterate over all the nums.

1.1. Code

class DSU():
    # O(N) T S
    def __init__(self, n):
        self.representatives = [i for i in range(n)]
        self.sizes = [1]*n
    
    # O(a(N)) T
    def find(self, x):
        if self.representatives[x] == x: return x
        self.representatives[x] = self.find(self.representatives[x])
        return self.representatives[x]

    # O(a(N)) T
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        
        if x == y: return
        if self.sizes[x] > self.sizes[y]: x, y = y, x
        
        self.representatives[x] = y
        self.sizes[y] += self.sizes[x]


class Solution:
    # Time: O(N * N * log(N) * a(N))
    # Space: O(N)
    def largestComponentSize(self, nums: List[int]) -> int:
        n = len(nums)
        dsu = DSU(n)
        
        for i in range(n): # O(N)
            for j in range(i): # O(N)
                if gcd(nums[i], nums[j]) != 1: # O(log(N))
                    dsu.unite(i, j) # O(a(N))
        
        # print(dsu.representatives)
        # print(dsu.sizes)
        return max(dsu.sizes)

1.2. Complexity Analysis

• Time: O(N * N * log(N) * a(N)), as explained in the code (commented). a(N) is the inverse ackermann function. Its value can be assumed 4 for all practical purposes.
• Space: O(N).

2. Largest Component Size by Common Factor: Observations & Logic

2.0. Intuitions

Let’s zoom into what we did for the bruteforce solution.

We first pick a number, say 21, and then try to connect it to the rest of the elements.

In case we do find a GCD > 1, we add an edge, connecting the two numbers.

Then we move onto the next number, say 10 and do the process again and again.

Finally, we see 2 total connected components of the sizes 2 and 3 respectively. We return 3 as the answer.

2.1. Optimizations

The first question is … where even do we optimize?

Since we have an O(N*N) nested loop, let’s try to optimize that.

All right. Now, its clear that we need to change the structure somehow. What if, we first find all the factors for num1, instead of finding the gcd for num1 and num2?

It’s a simple change in the sequence, and we can see what to do about the num2 thing.

Writing down all the factors of the numbers give us the following:

Do you notice something in the yellow row? There’s a lot of repetition!

So let’s write it more neatly.

Great! It looks good, but now what?

If you notice, the 4, 10, 5 chain and the 21, 49 that has just formed is the exact same as the connected components?

3. Largest Component Size by Common Factor: Optimized Implementation

3.0. Code

class DSU():
    # O(N) T S
    def __init__(self, n):
        self.representatives = [i for i in range(n)]
        self.sizes = [1]*n
    
    # O(a(N)) T
    def find(self, x):
        if self.representatives[x] == x: return x
        self.representatives[x] = self.find(self.representatives[x])
        return self.representatives[x]

    # O(a(N)) T
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        
        if x == y: return
        if self.sizes[x] > self.sizes[y]: x, y = y, x
        
        self.representatives[x] = y
        self.sizes[y] += self.sizes[x]

class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        n = len(nums)
        dsu = DSU(n)
        
        def get_factors(num):
            ans = set()
            i = 2
            while i*i <= num:
                if num%i == 0:
                    ans.add(i)
                    num //= i
                else:
                    i += 1
            ans.add(num)
            return list(ans)
    
    
        primes = defaultdict(list)
        for i, num in enumerate(nums):
            factors = get_factors(num)
            for factor in factors:
                primes[factor].append(i)
        
        for indices in primes.values():
            for i in range(len(indices)-1):
                dsu.unite(indices[i], indices[i+1])
        
        return max(dsu.sizes)

3.1. Complexity Analysis

will be added soon!

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.