GCD Sort of an Array

GCD Sort of an Array

What is this problem about?

The GCD Sort of an Array coding problem asks if you can sort an array in non-decreasing order using a specific swap operation. You are allowed to swap any two elements nums[i] and nums[j] if their Greatest Common Divisor (GCD) is strictly greater than 1. You can perform this swap any number of times.

Why is this asked in interviews?

Amazon asks this Hard difficulty Math and Graph problem to test your knowledge of Union Find (Disjoint Set) and prime factorization. It evaluates your ability to recognize that if elements can be swapped, they belong to the same "connected component." The problem boils down to checking if the original element and the element that should be in its place after sorting belong to the same component.

Algorithmic pattern used

This problem uses Union Find and Sieve of Eratosthenes.

1. Prime Factorization: For each number in the array, find its prime factors.
2. Union Find: Create a Disjoint Set Union (DSU). Union each number with its prime factors. This groups numbers that share a common prime factor (GCD > 1), and transitively groups numbers connected by a chain of swaps.
3. Validation: Create a sorted copy of the original array. Iterate through the indices. If original[i] != sorted[i], they must be in the same DSU component to be swappable. If they aren't, return False.

Example explanation

nums = [7, 21, 3]

1. Primes of 7: {7}.
2. Primes of 21: {3, 7}.
3. Primes of 3: {3}.
4. Union Find:
   • Union(7, 7)
   • Union(21, 3), Union(21, 7)
   • Union(3, 3) Because 21 shares 7 with 7, and 3 with 3, all numbers {3, 7, 21} are in the same component!
5. Sorted: [3, 7, 21].
6. Since all numbers are in the same component, they can be freely swapped into any order. Return True.

Common mistakes candidates make

• $O(N^2)$ GCD Checks: Trying to check the GCD of every pair of elements to build the graph. For $N=3 imes 10^4$, this is too slow.
• Inefficient Union Find: Not using Path Compression and Union by Rank/Size, leading to slow find operations.
• Factorizing naively: Finding prime factors up to $N$ instead of using a precomputed sieve or just checking up to $\sqrt{N}$.

Interview preparation tip

Whenever a problem says "you can swap A and B if they share a property, can you reach state X?", it is almost always a Union Find problem. The swappable items form a connected component, and you just need to verify that items only need to move within their own component.