LeetCode in Kotlin

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.

Solution

import kotlin.math.sqrt

class Solution {
    fun largestComponentSize(nums: IntArray): Int {
        var max = 0
        for (a in nums) {
            max = Math.max(max, a)
        }
        val roots = IntArray(max + 1)
        val sizes = IntArray(max + 1)
        for (idx in 1..max) {
            roots[idx] = idx
        }
        for (a in nums) {
            if (a == 1) {
                sizes[a] = 1
                continue
            }
            val sqrt = sqrt(a.toDouble()).toInt()
            val thisRoot = getRoot(roots, a)
            sizes[thisRoot]++
            for (factor in 1..sqrt) {
                if (a % factor == 0) {
                    val otherFactor = a / factor
                    val otherFactorRoot = getRoot(roots, otherFactor)
                    if (factor != 1) {
                        union(roots, thisRoot, factor, sizes)
                    }
                    union(roots, thisRoot, otherFactorRoot, sizes)
                }
            }
        }
        var maxConnection = 0
        for (size in sizes) {
            maxConnection = Math.max(maxConnection, size)
        }
        return maxConnection
    }

    private fun union(roots: IntArray, a: Int, b: Int, sizes: IntArray) {
        val rootA = getRoot(roots, a)
        val rootB = getRoot(roots, b)
        if (rootA != rootB) {
            sizes[rootA] += sizes[rootB]
            roots[rootB] = rootA
        }
    }

    private fun getRoot(roots: IntArray, a: Int): Int {
        if (roots[a] == a) {
            return a
        }
        roots[a] = getRoot(roots, roots[a])
        return roots[a]
    }
}

This site is open source. Improve this page.