LeetCode 1998 - GCD Sort of an Array

LeetCode Problem 1998

Difficulty: 🔴 Hard
Topics: Array, Math, Union-Find, Sorting, Number Theory

Solution

Problem Understanding

The problem asks whether it is possible to sort an integer array nums into non-decreasing order using a very specific type of swap. You can swap any two elements nums[i] and nums[j] if and only if their greatest common divisor (GCD) is greater than 1. The input is an array of integers ranging from 2 up to 100,000, with a length up to 30,000. The expected output is a boolean, true if it is possible to sort the array using any number of such swaps, or false otherwise.

The key insight is that the operation is not arbitrary; it is restricted by number-theoretic properties. This means two elements can only interact through a chain of swaps if they share a common prime factor. Therefore, whether sorting is possible depends on the connectivity between numbers through shared prime factors.

Edge cases to consider include arrays that are already sorted, arrays where some elements are prime and cannot interact with others, and arrays where all elements are multiples of a common factor.

Approaches

A naive brute-force approach would attempt to simulate all valid swaps. This would involve computing GCD for all possible pairs and swapping elements if allowed, repeating until no more swaps can be made. While this is logically correct, it is far too slow for the input constraints because the number of potential swaps is O(n²), and GCD computation for each pair can also be costly.

The optimal approach leverages number theory and union-find (disjoint set union, DSU). The observation is that elements can only move into positions of other elements that are in the same connected component, where connectivity is defined by sharing at least one prime factor. Using a sieve to factorize numbers efficiently, we can union all numbers that share a prime factor into the same component. After building these components, sorting is possible if, for each index, the sorted value and the original value belong to the same connected component.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² * log(max(nums)))	O(n)	Simulates swaps by checking GCD of all pairs, infeasible for large arrays
Optimal	O(n log(max(nums)) + n α(n))	O(n + max(nums))	Uses union-find with prime factorization to group swappable elements efficiently

Algorithm Walkthrough

Initialize Union-Find: Create a union-find (DSU) structure for all numbers up to the maximum value in nums. Each number initially is its own parent.
Sieve for Factorization: Use a sieve of Eratosthenes or a similar factorization technique to find all prime factors of numbers up to max(nums). For each number, union it with its prime factors to link all numbers sharing the same prime.
Union Connected Numbers: Iterate over the nums array. For each number, find its prime factors and union the number with each prime. This builds components where numbers in the same component can be swapped.
Check Sort Feasibility: Create a sorted copy of nums. For each index i, check if nums[i] and sorted_nums[i] belong to the same component. If any element does not share a component with its sorted position, return false.
Return True: If all elements can be swapped to their sorted positions through connected components, return true.

Why it works: This approach guarantees correctness because the union-find components precisely capture which elements can reach which positions via valid GCD swaps. Any element that needs to move to a sorted position must be in the same connected component as that position; otherwise, no sequence of valid swaps can place it correctly.

Python Solution

from math import isqrt
from typing import List

class Solution:
    def gcdSort(self, nums: List[int]) -> bool:
        max_val = max(nums)
        parent = list(range(max_val + 1))
        
        def find(x: int) -> int:
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def union(x: int, y: int):
            parent[find(x)] = find(y)
        
        # Factorization and union with primes
        for num in nums:
            n = num
            for p in range(2, isqrt(num) + 1):
                if n % p == 0:
                    union(num, p)
                    while n % p == 0:
                        n //= p
            if n > 1:
                union(num, n)
        
        sorted_nums = sorted(nums)
        for a, b in zip(nums, sorted_nums):
            if find(a) != find(b):
                return False
        return True

Explanation: We first initialize the union-find structure with parent representing the leader of each component. The find function applies path compression for efficiency. The union function merges two components. For each number, we factorize it and union it with its prime factors, ensuring all numbers sharing primes are connected. Finally, we check whether each number can reach its sorted position by comparing component leaders.

Go Solution

func gcdSort(nums []int) bool {
    maxVal := 0
    for _, num := range nums {
        if num > maxVal {
            maxVal = num
        }
    }

    parent := make([]int, maxVal+1)
    for i := range parent {
        parent[i] = i
    }

    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }

    union := func(x, y int) {
        parent[find(x)] = find(y)
    }

    for _, num := range nums {
        n := num
        for p := 2; p*p <= n; p++ {
            if n%p == 0 {
                union(num, p)
                for n%p == 0 {
                    n /= p
                }
            }
        }
        if n > 1 {
            union(num, n)
        }
    }

    sortedNums := append([]int(nil), nums...)
    sort.Ints(sortedNums)

    for i := range nums {
        if find(nums[i]) != find(sortedNums[i]) {
            return false
        }
    }
    return true
}

Go-specific notes: The Go version handles slices explicitly and uses a closure for find to implement path compression. Prime factorization uses the same approach as Python. Sorting uses sort.Ints on a copied slice to avoid modifying the original.

Worked Examples

Example 1: nums = [7, 21, 3]

Factorize 7 → {7}, 21 → {3,7}, 3 → {3}.
Union: 7 ↔ 7, 21 ↔ 3,21 ↔ 7, 3 ↔ 3
Connected components: {3,21}, {7,21}
Sorted nums = [3,7,21]
Check index 0: 7 → 3, 7 and 3 are connected? Yes
Check index 1: 21 → 7, connected? Yes
Check index 2: 3 → 21, connected? Yes
Return True

Example 2: nums = [5,2,6,2]

Factorize 5 → {5}, 2 → {2}, 6 → {2,3}, 2 → {2}
Union components: {2,6}, {3,6}, {5}
Sorted nums = [2,2,5,6]
Check index 2: 6 → 5, 6 and 5 connected? No
Return False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log(max(nums)))	Factorization of each number up to sqrt(num), union-find operations almost O(1)
Space	O(n + max(nums))	Union-find array and space for primes/factors

The time complexity is dominated by factorizing all numbers and the union operations. The space is mainly for storing the parent array for union-find.

Test Cases

# test cases
sol = Solution()

assert sol.gcdSort([7,21,3]) == True  # swaps possible through shared prime factors
assert sol.gcdSort([5,2,6,2]) == False  # impossible to sort
assert sol.gcdSort([10,5,9,3,15]) == True  # multiple swaps allowed
assert sol.gcdSort([2,3,5,7,11]) == True  # already sorted primes
assert sol.gcdSort([11,7,5,3,2]) == False  # reverse primes cannot swap
assert sol.gcdSort([6,10,15]) == True  # all numbers share prime connectivity

Test	Why
`[7,21,3]`	Elements connected via shared prime factors, can sort
`[5,2,6,2]`	Element 5 cannot swap, cannot sort
`[10,5,9,3,15]`	Multiple swaps through prime factors
`[2,3,5,7,11]`	Already sorted, all primes
`[11,7,5