#1998

Hard

LeetCode Problem Workspace

GCD Sort of an Array

The GCD Sort problem challenges you to sort an array using a specific gcd-based swap method.

array math union find sorting number theory

Problem Statement

You are given an integer array nums, and you can perform the following operation any number of times: swap two elements nums[i] and nums[j] if and only if gcd(nums[i], nums[j]) > 1. Your task is to determine whether it is possible to sort nums in non-decreasing order using this swap method. Return true if it is possible, or false otherwise.

For example, with nums = [7, 21, 3], gcd(7, 21) = 7 and gcd(21, 3) = 3, allowing you to swap and ultimately sort the array. However, some arrays cannot be sorted due to no valid gcd-based swaps being possible.

Examples

Example 1

Input: nums = [7,21,3]

Output: true

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

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]`

Example details omitted.

Constraints

1 <= nums.length <= 3 * 104
2 <= nums[i] <= 105

Solution Approach

Graph Representation of Connections

By treating each number in the array as a node, you can represent valid swaps (based on gcd > 1) as edges between nodes. This transforms the problem into one of finding connected components, where all elements in a component can be freely swapped.

Union-Find Algorithm

A Union-Find (or Disjoint Set Union, DSU) algorithm is helpful in determining which elements can be connected via valid swaps. You can union numbers that share common factors and then check if the components can be arranged in sorted order.

Sorting Within Components

After identifying connected components, you can sort each component independently. Then, verify if these sorted components can match the target sorted array. If they do, sorting is possible; otherwise, it's not.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is influenced by the Union-Find algorithm, which is near-linear with path compression. Sorting the array and verifying components adds additional time, resulting in an overall complexity of O(n log n) due to sorting, where n is the length of the array.

What Interviewers Usually Probe

Look for a clear understanding of graph theory and its application to number theory problems.
Evaluate the candidate's ability to optimize Union-Find operations for efficiency.
Assess how the candidate handles edge cases where gcd connections are sparse or absent.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding gcd relationships can lead to incorrect union operations.
Failing to optimize the Union-Find structure for large inputs.
Not correctly checking if sorting is achievable once components are identified.

Follow-up variants

Consider variations where only some elements can be swapped (restricted gcd conditions).
What happens if you are given a fixed number of allowed swaps?
How would the problem change if instead of gcd, you had to check for divisibility?

FAQ

What is the main idea behind solving the GCD Sort problem?

The main idea is to treat the array elements as nodes in a graph, where an edge exists between two nodes if their gcd is greater than 1. Using Union-Find, we group elements that can be swapped and check if sorting is possible.

How does Union-Find help in the GCD Sort problem?

Union-Find is used to efficiently group elements that can be swapped due to having common factors. After identifying these groups, the elements within each group can be sorted independently.

What are some common pitfalls when solving the GCD Sort problem?

Some common pitfalls include incorrect handling of gcd conditions, inefficient Union-Find optimizations, and failing to verify if sorted components can match the target sorted array.

How can I optimize my Union-Find solution for the GCD Sort problem?

You can optimize Union-Find by using path compression and union by rank to ensure near-constant time operations, making it efficient for large inputs.

What is the complexity of the GCD Sort problem?

The time complexity is generally O(n log n), dominated by the sorting step. The Union-Find operations contribute a near-linear complexity due to optimizations like path compression.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def gcdSort(self, nums: List[int]) -> bool:
        n = 10**5 + 10
        p = list(range(n))
        f = defaultdict(list)
        mx = max(nums)
        for i in range(2, mx + 1):
            if f[i]:
                continue
            for j in range(i, mx + 1, i):
                f[j].append(i)

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        for i in nums:
            for j in f[i]:
                p[find(i)] = find(j)

        s = sorted(nums)
        for i, num in enumerate(nums):
            if s[i] != num and find(num) != find(s[i]):
                return False
        return True

Continue Practicing

#2280 minimum lines to represent a line chart #2344 minimum deletions to make array divisible #1627 graph connectivity with threshold