Problem statement

You are given an integer array nums. You may swap two elements nums[i] and nums[j] whenever gcd(nums[i], nums[j]) > 1, as many times as you like.

Return true if these swaps can sort nums into non-decreasing order, and false otherwise.

Example 1

Input: nums = [7,21,3]
Output: true
Explanation: Swap 7 and 21 (gcd 7) to get [21,7,3], then 21 and 3 (gcd 3) to get [3,7,21].

Example 2

Input: nums = [5,2,6,2]
Output: false
Explanation: 5 shares no factor with anything, so it can never leave the front, but it belongs in the last place.

Example 3

Input: nums = [10,5,9,3,15]
Output: true

Constraints

• 1 <= nums.length <= 3 * 10^4
• 2 <= nums[i] <= 10^5

Hints for GCD Sort of an Array

1. Hint 1

   Swaps compose: if a can swap with b and b with c, then a, b and c can be rearranged in any order. So what matters is which elements are connected through chains of shared factors.

2. Hint 2

   Connecting every pair is O(n²). Instead connect each number to its prime factors with a union-find: two numbers sharing a prime end up in one set.

3. Hint 3

   Compare nums with its sorted copy: the array can be sorted iff for every index i, nums[i] and sorted[i] are in the same set.

How to solve GCD Sort of an Array

Elements that can reach each other through gcd > 1 swaps form groups that can be permuted arbitrarily. Grouping goes through prime factors — a number joins the set of each of its primes — so union-find over values and primes builds the groups in near-linear time.

Approach

1. Create a union-find over 0 … max(nums).
2. Factor each number by trial division and union it with each of its prime factors.
3. Sort a copy of nums.
4. For every index i, check that nums[i] and sorted[i] have the same root; if any pair differs, return false.

Why it works

Within a connected group, adjacent-swap reasoning shows any permutation is reachable (swaps along a spanning tree generate every transposition). Sorting succeeds iff every position can receive the value the sorted array puts there, which happens exactly when that value comes from the same group as the value currently there — groups keep their multiset of positions, so the per-index check is necessary and sufficient.

Complexity

• Time — O(n · sqrt(V) + V)
• Space — O(V)

Pitfalls

• Union numbers with primes, not with each other pairwise — O(n²) gcds time out at 3 · 10^4.
• After trial division up to sqrt(x), a leftover x > 1 is itself a prime factor.
• Equal values are interchangeable even when they cannot move: an index check against the sorted copy handles duplicates correctly.

Reference solution

Python

from typing import List

def gcdSort(nums: List[int]) -> bool:
    parent = list(range(max(nums) + 1))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb

    for v in nums:
        x, p = v, 2
        while p * p <= x:
            if x % p == 0:
                union(v, p)
                while x % p == 0:
                    x //= p
            p += 1
        if x > 1:
            union(v, x)
    s = sorted(nums)
    return all(find(a) == find(b) for a, b in zip(nums, s))

Java

static int[] par;

static int find(int x) {
    while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
    return x;
}

static void union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra != rb) par[ra] = rb;
}

public static boolean gcdSort(int[] nums) {
    int mx = 0;
    for (int v : nums) mx = Math.max(mx, v);
    par = new int[mx + 1];
    for (int i = 0; i <= mx; i++) par[i] = i;
    for (int v : nums) {
        int x = v;
        for (int p = 2; p * p <= x; p++) {
            if (x % p == 0) {
                union(v, p);
                while (x % p == 0) x /= p;
            }
        }
        if (x > 1) union(v, x);
    }
    int[] s = nums.clone();
    Arrays.sort(s);
    for (int i = 0; i < nums.length; i++) if (find(nums[i]) != find(s[i])) return false;
    return true;
}

C++

vector<int> par;

int findRoot(int x) {
    while (par[x] != x) { par[x] = par[par[x]]; x = par[x]; }
    return x;
}

void unite(int a, int b) {
    int ra = findRoot(a), rb = findRoot(b);
    if (ra != rb) par[ra] = rb;
}

bool gcdSort(vector<int>& nums) {
    int mx = *max_element(nums.begin(), nums.end());
    par.assign(mx + 1, 0);
    for (int i = 0; i <= mx; i++) par[i] = i;
    for (int v : nums) {
        int x = v;
        for (int p = 2; p * p <= x; p++) {
            if (x % p == 0) {
                unite(v, p);
                while (x % p == 0) x /= p;
            }
        }
        if (x > 1) unite(v, x);
    }
    vector<int> s = nums;
    sort(s.begin(), s.end());
    for (size_t i = 0; i < nums.size(); i++) if (findRoot(nums[i]) != findRoot(s[i])) return false;
    return true;
}

JavaScript

var gcdSort = function(nums) {
    var mx = 0;
    for (var i = 0; i < nums.length; i++) if (nums[i] > mx) mx = nums[i];
    var parent = [];
    for (var j = 0; j <= mx; j++) parent.push(j);
    var find = function(x) {
        while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
        return x;
    };
    var union = function(a, b) {
        var ra = find(a), rb = find(b);
        if (ra !== rb) parent[ra] = rb;
    };
    for (var k = 0; k < nums.length; k++) {
        var v = nums[k], x = v;
        for (var p = 2; p * p <= x; p++) {
            if (x % p === 0) {
                union(v, p);
                while (x % p === 0) x = x / p;
            }
        }
        if (x > 1) union(v, x);
    }
    var s = nums.slice().sort(function(a, b) { return a - b; });
    for (var t = 0; t < nums.length; t++) if (find(nums[t]) !== find(s[t])) return false;
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard