GCD Sort of an Array - Solution & Explanation
Problem Statement
You are given an integer array nums, and you can perform the following operation any number of times on nums:
- Swap the positions of two elements
nums[i]andnums[j]ifgcd(nums[i], nums[j]) > 1wheregcd(nums[i], nums[j])is the greatest common divisor ofnums[i]andnums[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] <= 105
Approach Overview
Problem 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 1: Approach 1: Union-Find with Prime Decomposition
This approach involves decomposing each number into its prime factors and then using the Union-Find data structure to connect numbers based on shared prime factors. The key insight is to treat numbers as nodes and shared prime factors as edges in a graph, allowing us to check if we can sort the array by ensuring any number can swap with its desired position in the sorted array via a common factor.
This C code implements the Union-Find data structure combined with prime factor decomposition. We initialize parent pointers for all numbers, then for each number, we find its parent, forming connected components in which swaps are permissible. The sorted array is checked against this condition.
Complexity
Time Complexity: O(N log(N)), where N is the number of elements in nums, due to sorting and union-find operations. Space Complexity: O(M), where M is the upper limit of the number range (10^5).
Approach 2: Approach 2: Connected Components with Sieve
This approach leverages the Sieve of Eratosthenes to connect numbers sharing the same prime factors into connected components. Using these components, we assess if elements can shift positions based on common factor conditions for sorting.
In this C implementation, a version of the Sieve of Eratosthenes is used to determine prime factors and unite them in connected components using union-find. Sorting is validated by ensuring elements can belong to the same component
Complexity
Time Complexity: O(N log(N)), where N is the number of elements in nums, due to sorting and connected component operations. Space Complexity: O(M), where M is the upper limit of the number range (10^5).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Union-Find with Prime Decomposition | Time Complexity: O(N log(N)), where N is the number of elements in nums, due to sorting and union-find operations. Space Complexity: O(M), where M is the upper limit of the number range (10^5). |
| Approach 2: Connected Components with Sieve | Time Complexity: O(N log(N)), where N is the number of elements in nums, due to sorting and connected component operations. Space Complexity: O(M), where M is the upper limit of the number range (10^5). |
| Default Approach | — |
Detailed Complexity Analysis
| 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. |
Video Solution
LeetCode 1998. GCD Sort of an Array • Happy Coding • 2,490 views views
Watch 5 more video solutions →Frequently Asked Questions
Is GCD Sort of an Array easy or hard?
GCD Sort of an Array Python/Java solution
How to solve GCD Sort of an Array in O(n)?
What is the best approach for GCD Sort of an Array?
Is GCD Sort of an Array asked at Google/Amazon/Meta?
What data structure is used in GCD Sort of an Array?
What is the time complexity of GCD Sort of an Array?
Ready to solve this problem?
Practice GCD Sort of an Array with our built-in code editor and test cases.
Practice on FleetCode