Watch 7 video solutions for GCD Sort of an Array, a hard level problem involving Array, Math, Union Find. This walkthrough by Happy Coding has 2,424 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an integer array nums, and you can perform the following operation any number of times on nums:
nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j].Return true if it is possible to sort nums in non-decreasing order using the above swap method, or false otherwise.
Example 1:
Input: nums = [7,21,3] Output: true Explanation: We can sort [7,21,3] by performing the following operations: - Swap 7 and 21 because gcd(7,21) = 7. nums = [21,7,3] - Swap 21 and 3 because gcd(21,3) = 3. nums = [3,7,21]
Example 2:
Input: nums = [5,2,6,2] Output: false Explanation: It is impossible to sort the array because 5 cannot be swapped with any other element.
Example 3:
Input: nums = [10,5,9,3,15] Output: true We can sort [10,5,9,3,15] by performing the following operations: - Swap 10 and 15 because gcd(10,15) = 5. nums = [15,5,9,3,10] - Swap 15 and 3 because gcd(15,3) = 3. nums = [3,5,9,15,10] - Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,10,15]
Constraints:
1 <= nums.length <= 3 * 1042 <= nums[i] <= 105Problem Overview: You are given an integer array and can swap two elements only if their gcd(a, b) > 1. Determine whether the array can be rearranged into sorted order using any number of such swaps.
Approach 1: Union-Find with Prime Decomposition (≈ O(n log M) time, O(M) space)
The key observation: if two numbers share a common prime factor (directly or through a chain of other numbers), they can eventually be swapped. Model this using Union Find. For each number, compute its prime factors using trial division or a smallest-prime-factor array. Union the number with each of its prime factors. This builds connected components where numbers sharing factors belong to the same group. After building the structure, create a sorted copy of the array. For each index i, check if nums[i] and sorted[i] belong to the same union-find root. If every position satisfies this condition, the array can be sorted. The insight is that swaps are possible anywhere inside a component because a chain of valid gcd swaps exists.
This approach combines number theory (prime factorization) with disjoint-set connectivity. Union operations connect numbers through shared factors, while path compression keeps operations nearly constant time. This is the most common interview solution because it directly models the swap constraints.
Approach 2: Connected Components with Sieve (≈ O(M log log M + n log M) time, O(M) space)
Instead of factoring each number individually, precompute smallest prime factors for all numbers up to the maximum value using a sieve. This converts factorization from repeated division into fast lookups. Iterate through the array and factor each value using the sieve table. As with the previous approach, union the value with each of its prime factors so that numbers sharing factors fall into the same component. After building components, compare the original array with the sorted array and verify that corresponding values belong to the same root.
The sieve reduces repeated factorization work when the maximum value is large. This method is essentially the same connectivity idea but optimized with precomputation. It is commonly paired with array processing and sorting checks to validate whether every element can move to its sorted position.
Recommended for interviews: Union-Find with prime factor decomposition is the expected approach. Start by explaining why swaps create connectivity groups based on shared prime factors. Brute-force pairwise gcd checks show understanding but scale poorly. Demonstrating union-find with factorization shows mastery of both graph connectivity and number theory optimization.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find with Prime Decomposition | O(n log M) | O(M) | General case. Standard interview solution using union-find and factorization. |
| Connected Components with Sieve | O(M log log M + n log M) | O(M) | Better when many numbers share large ranges and repeated factorization would be expensive. |