LeetCode Solutions Blog

GCD Sort of an Array

Number: 2125

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given an integer array nums, you can swap any two elements nums[i] and nums[j] if the greatest common divisor of nums[i] and nums[j] is greater than 1. Determine if it is possible to sort the array in non-decreasing order using these swaps.

Key Insights

Two numbers can be swapped if they share a common prime factor (gcd > 1), which establishes a connection between them.
The connections form groups (or connected components) where elements can be reordered arbitrarily.
Union Find (Disjoint Set Union) is used to group indices that are connected based on common prime factors.
After grouping, by sorting elements within each connected component, we can compare with the fully sorted array to verify if a global sort is possible.
Prime factorization is key to determine the connectivity between numbers.

Space and Time Complexity

Time Complexity: O(n * log(max(nums)) + n α(n)) – Prime factorization has a logarithmic complexity per element and union-find operations are nearly constant (α(n)).
Space Complexity: O(n + max(nums)) – Extra space is used to maintain union-find arrays and mappings for factors.

Solution

The algorithm uses a union-find data structure to group indices of numbers that share a common prime factor. For each number, we perform prime factorization and union its index with indices of previously seen numbers sharing the same factor. Each group (or connected component) can be internally sorted. Finally, we create a sorted copy of the original array and check if by reordering numbers within each connected component, the overall sorted order is achieved. If yes, return true; otherwise, false.

Code Solutions

def gcdSort(nums):
    n = len(nums)
    
    # Helper function to compute prime factors of x.
    def prime_factors(x):
        factors = set()
        while x % 2 == 0:
            factors.add(2)
            x //= 2
        f = 3
        while f * f <= x:
            if x % f == 0:
                factors.add(f)
                x //= f
            else:
                f += 2
        if x > 1:
            factors.add(x)
        return factors

    # Union-Find initialization.
    parent = list(range(n))
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            parent[rootY] = rootX

    # Map each prime factor to an index where it was first seen.
    factor_to_index = {}
    for i in range(n):
        for factor in prime_factors(nums[i]):
            if factor in factor_to_index:
                union(i, factor_to_index[factor])
            else:
                factor_to_index[factor] = i

    # Group indices by their union-find parent.
    groups = {}
    for i in range(n):
        root = find(i)
        groups.setdefault(root, []).append(i)

    # Create a sorted copy of the array.
    sorted_nums = sorted(nums)
    
    # For each connected component, compare sorted group values with sorted array positions.
    for indices in groups.values():
        group_vals = sorted([nums[i] for i in indices])
        sorted_group_vals = sorted([sorted_nums[i] for i in sorted(indices)])
        if group_vals != sorted_group_vals:
            return False
    return True

# Example usage:
print(gcdSort([7,21,3]))  # Output: True
print(gcdSort([5,2,6,2])) # Output: False