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.

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.

Python Solution

1from collections import defaultdict
2
3class Solution:
4    def gcdSort(self, nums: List[int]) -> bool:
5        # Define a constant for the maximum integer value, which is slightly above 10**5.
6        max_value = 10**5 + 10
7        # Initialize a parent array for the disjoint set (union-find) data structure.
8        parent = list(range(max_value))
9        # Create a dictionary to hold the prime factors for each element.
10        factor_dict = defaultdict(list)
11        # Get the maximum element from the input list for setting bounds in the sieve.
12        highest_value = max(nums)
13        # Use a modified Sieve of Eratosthenes to find factors.
14        for i in range(2, highest_value + 1):
15            if factor_dict[i]:
16                continue
17            for j in range(i, highest_value + 1, i):
18                factor_dict[j].append(i)
19      
20        # Define the function to find the root parent in the union-find structure.
21        def find_set(x):
22            if parent[x] != x:
23                parent[x] = find_set(parent[x])
24            return parent[x]
25      
26        # Union operation — connect the first prime factor of each number to the number itself.
27        for number in nums:
28            for factor in factor_dict[number]:
29                parent[find_set(number)] = find_set(factor)
30      
31        # Sort the input list to compare it against the original list.
32        sorted_nums = sorted(nums)
33        # Check if each element is properly connected through a common factor.
34        for i, num in enumerate(nums):
35            if sorted_nums[i] != num and find_set(num) != find_set(sorted_nums[i]):
36                # If an element is not connected to its corresponding element in
37                # the sorted list through a prime factor, sorting is not possible.
38                return False
39        # If all elements are connected, then GCD sort is possible.
40        return True
41

Java Solution

1class Solution {
2
3    // The array 'parent' holds the representative item for the disjoint set (union-find).
4    private int[] parent;
5
6    public boolean gcdSort(int[] nums) {
7        // The maximum limit for the numbers in the array nums.
8        int upperLimit = 100010;
9      
10        // Initialize the parent array for union-find
11        parent = new int[upperLimit];
12      
13        // A map to store factors of each number as a list.
14        Map<Integer, List<Integer>> factors = new HashMap<>();
15      
16        // Initially, each number is its own parent.
17        for (int i = 0; i < upperLimit; ++i) {
18            parent[i] = i;
19        }
20      
21        // Find the maximum number in nums to limit the sieve.
22        int maxNum = 0;
23        for (int num : nums) {
24            maxNum = Math.max(maxNum, num);
25        }
26      
27        // Sieve of Eratosthenes: populate factors map with prime factors for numbers up to maxNum.
28        for (int i = 2; i <= maxNum; ++i) {
29            if (factors.containsKey(i)) {
30                continue;
31            }
32            for (int j = i; j <= maxNum; j += i) {
33                factors.computeIfAbsent(j, k -> new ArrayList<>()).add(i);
34            }
35        }
36      
37        // Union the sets of each number and its prime factors.
38        for (int i : nums) {
39            for (int j : factors.get(i)) {
40                union(find(i), find(j));
41            }
42        }
43      
44        // Create a sorted array 'sortedNums' from 'nums' using array copy.
45        int[] sortedNums = new int[nums.length];
46        System.arraycopy(nums, 0, sortedNums, 0, nums.length);
47        Arrays.sort(sortedNums);
48      
49        // Check if each element and its sorted counterpart have the same parent.
50        for (int i = 0; i < nums.length; ++i) {
51            if (sortedNums[i] != nums[i] && find(nums[i]) != find(sortedNums[i])) {
52                return false; // Not possible to sort using GCD operations.
53            }
54        }
55        return true; // Possible to sort using GCD operations.
56    }
57
58    // Find the representative of the set to which 'x' belongs.
59    int find(int x) {
60        if (parent[x] != x) {
61            parent[x] = find(parent[x]);
62        }
63        return parent[x];
64    }
65  
66    // Union operation for union-find, unites two subsets into a single subset.
67    void union(int x, int y) {
68        parent[find(x)] = find(parent[y]);
69    }
70}
71

C++ Solution

1#include <vector>
2#include <algorithm>
3#include <unordered_map>
4using namespace std;
5
6class Solution {
7public:
8    vector<int> parent; // Using 'parent' for representing the disjoint set 
9
10    // Method to check if it's possible to sort array by GCD operations
11    bool gcdSort(vector<int>& nums) {
12        int maxSize = 100010; // Define the upper limit for the size
13        parent.resize(maxSize);
14        // Initialize the disjoint set such that each node is its own parent
15        for (int i = 0; i < maxSize; ++i) parent[i] = i;
16
17        int maxNum = 0; // Keep track of the maximum number in the array
18        for (auto num : nums) maxNum = max(maxNum, num);
19
20        // Map to store the factors of each number up to the maximum number
21        unordered_map<int, vector<int>> factors;
22        for (int i = 2; i <= maxNum; ++i) {
23            if (!factors[i].empty()) continue;
24            for (int j = i; j <= maxNum; j += i) factors[j].push_back(i);
25        }
26
27        // Union operations on the elements and their factors
28        for (int num : nums) {
29            for (int factor : factors[num]) parent[find(num)] = find(factor);
30        }
31
32        // Sort the original array without modifying it
33        vector<int> sortedNums = nums;
34        sort(sortedNums.begin(), sortedNums.end());
35
36        // Compare the sorted array with the original array
37        for (int i = 0; i < nums.size(); ++i) {
38            // If an element and its sorted counterpart don't belong to the same set,
39            // then we cannot sort the array using GCD operations.
40            if (sortedNums[i] != nums[i] && find(sortedNums[i]) != find(nums[i])){
41                return false;
42            }
43        }
44        // If all elements can be sorted using GCD operations, return true
45        return true;
46    }
47
48    // Method to find the root parent of an element 'x' using path compression
49    int find(int x) {
50        if (parent[x] != x) parent[x] = find(parent[x]);
51        return parent[x];
52    }
53};
54

Typescript Solution

1// Import necessary components, if needed, e.g. for a TypeScript version of this solution.
2// import ...
3
4// Global variable to represent the disjoint set
5let parent: Array<number> = [];
6
7// Function to find the root parent of an element 'x' with path compression
8function find(x: number): number {
9  if (parent[x] !== x) {
10    parent[x] = find(parent[x]);
11  }
12  return parent[x];
13}
14
15// Function to check if it's possible to sort array using GCD operations
16function gcdSort(nums: Array<number>): boolean {
17  let maxSize: number = 100010; // Define the upper limit for the size
18  parent = new Array(maxSize).fill(0).map((_, index) => index); // Initialize parent array
19
20  let maxNum: number = 0; // Keep track of the maximum number in the array
21  for (let num of nums) {
22    maxNum = Math.max(maxNum, num);
23  }
24
25  // Map to store the factors of each number up to the maximum number
26  let factors: { [key: number]: Array<number> } = {};
27  for (let i: number = 2; i <= maxNum; ++i) {
28    if (factors[i]) continue; // Skip if factors already exist
29
30    factors[i] = [];
31    for (let j: number = i; j <= maxNum; j += i) {
32      if (!factors[j]) factors[j] = [];
33      factors[j].push_back(i);
34    }
35  }
36
37  // Perform union operations on the elements and their factors
38  for (let num of nums) {
39    for (let factor of factors[num]) {
40      parent[find(num)] = find(factor);
41    }
42  }
43
44  // Create a sorted copy of the original array
45  let sortedNums: Array<number> = [...nums];
46  sortedNums.sort((a, b) => a - b);
47
48  // Compare the sorted array with the original array
49  for (let i: number = 0; i < nums.length; ++i) {
50    // If a pair of elements don't belong to the same set, sorting is not possible
51    if (sortedNums[i] !== nums[i] && find(sortedNums[i]) !== find(nums[i])) {
52      return false;
53    }
54  }
55
56  // If all elements can potentially be sorted via GCD operations, return true
57  return true;
58}
59

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).


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫