1998. GCD Sort of an Array

Problem Description

The task presented involves sorting an integer array nums but with a specific constraint on how the elements can be swapped. The standard sorting operations are not permitted. Instead, you may only swap two elements nums[i] and nums[j] if the greatest common divisor (GCD) of these elements is greater than 1.

The goal is to determine if it's possible to sort the given array into non-decreasing order by applying the restricted swap operation any number of times. If the array can be sorted within these constraints, you should return true, otherwise false.

The challenge in this problem lies in finding a way to determine if a sequence of swaps meeting the specified GCD condition can be made to sort the array. On the surface, it's not obvious how to utilize the GCD condition to facilitate sorting.

Intuition

The solution to this problem leverages the Union-Find data structure, which is a highly efficient data structure for tracking elements which are 'connected' or 'grouped' in some way. In the context of this problem, two numbers are considered connected if they can be swapped, which is determined by whether their GCD is greater than 1.

To approach this problem, we effectively build a graph where each number in the given array is a node, and a direct connection (edge) exists between two nodes if their GCD is greater than 1. This graph construction is abstract and doesn't need to be explicitly created; it is implicitly managed through the Union-Find structure. If two numbers can be connected through a chain of such edges, they can be swapped by a sequence of operations, even if they don't directly have a GCD greater than 1 with each other.

The Union-Find structure helps in grouping numbers that can be swapped with each other. For sorting to be possible, for every element nums[i], there must be a way to reach its target position, which is the position of the same number in the sorted array. If for a given pair of elements nums[i] and the element at the same position in the sorted array, they don't belong to the same group (i.e., no swappable path exists), the array can't be sorted, and we return false.

The solution code initializes Union-Find for an appropriately large array to capture all possible values, iterates over each prime number to connect numbers that share that prime factor, and then it verifies whether each number in nums can be swapped to its respective position in the sorted array.

Learn more about Union Find, Math and Sorting patterns.

Solution Approach

The solution uses the Union-Find algorithm, also known as Disjoint Set Union (DSU), to solve this problem. The Union-Find algorithm keeps track of elements which are part of the same set and allows us to efficiently determine whether two elements are in the same set or not. Additionally, it provides a way to union two different sets into a single set. In this case, if we can swap two elements by following a series of gcd conditions, we think of them as being in the same set.

Here is an in-depth look at the steps of the algorithm:

1. Initialization:

   • A list p represents the parent pointers for each node (initialized to point to themselves). This is used to track the root of each set.
   • A dictionary f collects lists of prime factors for the numbers up to the maximum number in nums.

2. Finding Prime Factors:

   • We loop through all numbers from 2 to the maximum number in nums to calculate the prime factors for each number. If a number has no prime factors listed in f yet, we know it is prime, and then we store it as a prime factor for all multiples of that number.

3. Creating the Union-Find Sets:

   • For each number in nums, we find its prime factors using dictionary f.
   • We then union all numbers with a shared prime factor by setting their parent pointer to a common root. This is equivalent to saying that all numbers sharing a prime factor can be part of a single swappable group.

4. Find Function:

   • The find function is crucial to the DSU. It recursively finds the root parent for any given node. Path compression is used as an optimization -- when we find the root, we set the parent pointer of all traversed nodes directly to the root, which flattens the structure and speeds up subsequent queries.

5. Checking If Sorting Is Possible:

   • We create a sorted version of nums called s.
   • For each element in nums, we check if the current element and the corresponding element in s have the same root parent. If they do, they are in the same set, and it is possible to swap these numbers (directly or through a series of swaps).
   • If at any point, an element in nums does not have the same set representative as its counterpart in s, it indicates that sorting is not possible, and the function returns false.

6. Returning the Result:

   • If all elements can be connected to their correct sorted positions through sets, the array can be sorted, so the function returns true.

By utilizing the Union-Find data structure, the solution efficiently groups numbers into sets of swappable elements, then checks whether elements can be moved to their sorted position through swaps within these sets.

Example Walkthrough

Let's use a small example to walk through the solution approach. Consider the array nums = [4, 9, 6, 3]. Our goal is to determine if we can sort nums into non-decreasing order using restricted swaps.

1. Initialization:

   • We initialize a Union-Find structure with parent pointers for each distinct element in nums. Suppose p looks like this after initialization: {4: 4, 9: 9, 6: 6, 3: 3}. Each number is initially its own parent.

2. Finding Prime Factors:

   • We process each number up to the maximum in nums, which is 9. Let's say our factor dictionary f looks like this after processing: {1: [], 2: [2], 3: [3], 4: [2], 5: [5], 6: [2, 3], 7: [7], 8: [2], 9: [3]}.

3. Creating the Union-Find Sets:

   • Looking at nums, we connect 4 and 6 because they share the prime factor 2. Now our Union-Find has {4: 4, 9: 9, 6: 4, 3: 3} indicating that 6 has parent 4.
   • We also connect 6 and 3 since they share the prime factor 3, this means the parent of 3 becomes 4 as well, so p is {4: 4, 9: 9, 6: 4, 3: 4}.
   • 9 has the same prime factor as 3 and is also connected, resulting in a single connected component {4: 4, 9: 4, 6: 4, 3: 4}.

4. Find Function:

   • For element 6, calling find(6) would trace up the parent pointers to find 4. Since path compression is applied, all members of this set would directly point to 4 after the find operation.

5. Checking If Sorting Is Possible:

   • The sorted version of nums is [3, 4, 6, 9]. We iterate through the elements of nums and their corresponding elements in sorted array s.
   • 4 in nums is at the position of 3 in s. Since 4 and 3 have the same root and are connected, a swap is possible.
   • 9 in nums is at the position of 4 in s. They are connected and can be swapped.
   • 6 in nums is at the position of 6 in s, and they are inherently in the same set.
   • Last, 3 in nums is at the position of 9 in s, and they are connected and thus swappable.

6. Returning the Result:

   • Since elements in nums can all be matched with their sorted position through the Union-Find sets, swapping is possible, and we return true.

By using the Union-Find data structure, we have identified that each number can be swapped with a sequence of swaps to reach its target position. Hence, sorting the array nums = [4, 9, 6, 3] under the given constraints is possible.

Solution Implementation

Time and Space Complexity

The provided code snippet defines a function gcdSort which checks if it's possible to sort an array nums by only making GCD operations. The time and space complexities are analyzed below.

Time Complexity:

Let "N" be the length of nums and "M" be the maximum value in nums.

1. Preprocessing primes up to mx (the maximum number in nums): This outer loop runs from 2 to mx and the inner loop marks each multiple of a prime. The inner loop's total iterations in worst case is O(M log(log M)) for the Sieve of Eratosthenes.

2. The union-find structure setup requires O(N) for iterating through nums and within this loop, we are performing union operations that require finding the roots of elements. There are at most O(log N) to find the root of a set in the union-find structure with path compression.

3. Sorting the array nums takes O(N log N).

4. The final loop compares sorted and unsorted arrays and performs find operations. The loop runs N times, and a find operation takes O(log N) at most.

From all these steps, sorting the array is the most expensive operation in general. However, for large values of "M", the sieve part may dominate. So the overall time complexity will be O(M log(log M) + N log N).

Space Complexity:

1. A list of size "n" (which equals 10^5+10, an arbitrary constant) for the parent pointers in the union-find structure: O(10^5) which is essentially O(1) since it doesn't depend on N or M.

2. A list of size "n" for storing found primes: same as above, O(10^5) which is essentially O(1).

3. A dictionary that can potentially store all prime factors for all numbers up to "M": this can be significant, but since we only store prime factors and each number <= M has O(log M) primes, the space complexity here is O(M log M).

4. The space for the sorted array s, which is O(N).

Combining these, the space complexity of the algorithm is dominated by the dictionary holding the factors, and is O(M log M + N).

Learn more about how to find time and space complexity quickly using problem constraints.