[leetcode #952] Largest Component Size by Common Factor

Problem

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 * 10⁴
・ 1 <= nums[i] <= 10⁵
・ All the values of nums are unique.

Idea

공배수를 가진 수끼리 연결해 그래프를 만들 때 그래프를 이루는 원소의 크기가 최대가 되는 경우를 구하는 문제다.

그래프와 관련된 문제의 난이도는 대부분이 Hard다. 하지만 어렵다고 안 풀 수도 없는 것이, 이와 비슷한 문제가 구글 알고리즘 문제에도 출제된 적이 있기 때문이다.

물론 이번에도 문제를 못 풀어서 Youtube를 보며 이해를 하고 풀었다. (Reference에 링크가 있다.)

우선 주어진 수의 최대값을 구하고, (최대값의 크기+1)만큼의 int array를 멤버 변수로 가지는 UnionFind instance를 만든다. 이 int array는 각 원소가 어떤 그룹에 속하는지 판단할 수 있는 parent값을 저장한다.

주어진 수를 차례로 돌면서 공배수를 가지는 수끼리 묶기 위해 약수를 차례로 구하고 서로 묶이는 그래프의 최소값을 parent로 만들어 저장한다. 주어진 수의 parent와 약수의 parent를 구하고, 두 parent 값이 서로 다를 경우 주어진 수의 parent를 약수의 parent로 치환한다. 이와 같은 과정을 거치는 이유는 주어진 수가 약수로 나누어지기 때문에 하나의 그래프로 묶이기 때문이다. parent를 구할 때는 parent의 parent가 있는지 재귀함수를 계속 호출해 확인하고 가장 상위 단계까지 갔을 때의 값을 리턴한다.

이 과정을 마치면 각 원소의 parent값이 UnionFind에 저장된다.

마지막으로, parent에 해당하는 값을 key로 하는 map을 만든다. 주어진 수를 다시 돌면서 parent를 구하고 map에 해당 parent가 등장한 빈도수를 저장한다. 각 parent 중 빈도수가 가장 큰 값을 가지는 것이 가장 많은 원소를 가진 그래프가 되며, 원소의 개수가 바로 문제가 원하는 답이다.

Solution

class Solution {
    private class UnionFind {
        int[] parent;

        UnionFind(int n) {
            parent = new int[n];
            for (int i=0; i < n; i++) {
                parent[i] = i;
            }
        }

        private int findAbsoluteParent(int elem) {
            if (parent[elem] == elem)
                return elem;

            parent[elem] = findAbsoluteParent(parent[elem]);

            return parent[elem];
        }

        private void unify(int i, int j) {
            int absoluteParentOfI = findAbsoluteParent(i);
            int absoluteParentOfJ = findAbsoluteParent(j);

            if (absoluteParentOfI != absoluteParentOfJ) {
                parent[absoluteParentOfJ] = absoluteParentOfI;
            }
        }
    }

    public int largestComponentSize(int[] nums) {

        // 1. find max value of nums
        int max = 0;
        for (int el : nums) {
            max = Math.max(max, el);    
        }

        // 2. Construct UnionFind instance
        UnionFind uf = new UnionFind(max+1);

        // 3. set absolute parents for each elements
        for (int el : nums) {
            for (int i=2; i*i <= el; i++) {
                if (el % i == 0) {
                    uf.unify(i, el);
                    uf.unify(el/i, el);
                }
            }
        }

        // 4. find the group which contains maximum number of elements
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int el : nums) {
            int absoluteParent = uf.findAbsoluteParent(el);
            map.put(absoluteParent, map.getOrDefault(absoluteParent, 0)+1);
            res = Math.max(res, map.get(absoluteParent));
        }

        return res;
    }
}

Reference

https://leetcode.com/problems/largest-component-size-by-common-factor/
https://www.youtube.com/watch?v=2WIhlxlY84Q
https://github.com/Sunchit/Coding-Decoded/blob/master/November2021/LargestComponentSizeByCommonFactor.java