LeetCode 1998: GCD Sort of an Array Solution

Master LeetCode problem 1998 (GCD Sort of an Array), 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.

1998. GCD Sort of an Array

Hard

Array Math Union Find Sorting Number Theory

Problem Explanation

Explanation

To solve this problem, we can use the concept of Disjoint Set Union (DSU) along with the Sieve of Eratosthenes to pre-calculate all the possible gcd values for the given range of numbers. We will then iterate through the input array and for each pair of elements where their gcd is greater than 1, we will union their sets in DSU. Finally, we will check if all elements that should be in the same set are in the same set. If so, we can sort the array, otherwise, it is impossible to sort it using the given swap operation.

Time complexity analysis:

Building the DSU structure: O(N * sqrt(max(nums))) where N is the number of elements in the input array and sqrt(max(nums)) is the maximum possible value for gcd.
Processing the input array: O(N * alpha(N)) where alpha(N) is the inverse Ackermann function which is considered to be effectively constant.
Overall time complexity: O(N * sqrt(max(nums)))

Space complexity: O(max(nums))

Solution Code

class Solution {
    int[] parent;

    public boolean gcdSort(int[] nums) {
        int n = nums.length;
        int maxNum = 100001; // maximum number possible
        parent = new int[maxNum];
        for (int i = 0; i < maxNum; i++) {
            parent[i] = i;
        }

        boolean[] isPrime = new boolean[maxNum];
        Arrays.fill(isPrime, true);
        for (int i = 2; i < maxNum; i++) {
            if (isPrime[i]) {
                for (int j = i * 2; j < maxNum; j += i) {
                    isPrime[j] = false;
                    union(i, j);
                }
            }
        }

        Map<Integer, List<Integer>> groups = new HashMap<>();
        for (int num : nums) {
            int root = find(num);
            groups.computeIfAbsent(root, k -> new ArrayList<>()).add(num);
        }

        for (List<Integer> group : groups.values()) {
            Collections.sort(group);
        }

        int[] sortedNums = new int[n];
        int index = 0;
        for (int num : nums) {
            int root = find(num);
            sortedNums[index++] = groups.get(root).remove(0);
        }

        for (int i = 1; i < n; i++) {
            if (sortedNums[i] < sortedNums[i - 1]) {
                return false;
            }
        }

        return true;
    }

    private void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootA] = rootB;
        }
    }

    private int find(int a) {
        if (parent[a] != a) {
            parent[a] = find(parent[a]);
        }
        return parent[a];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1998 (GCD Sort of an Array)?

This page provides optimized solutions for LeetCode problem 1998 (GCD Sort of an Array) 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 1998 (GCD Sort of an Array)?

The time complexity for LeetCode 1998 (GCD Sort of an Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1998 on DevExCode?

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

Back to LeetCode Solutions