Problem Description

You have an array of integers nums where each element is at a specific index (0-indexed). You can move between two indices i and j (where i ≠ j) only if the greatest common divisor (GCD) of nums[i] and nums[j] is greater than 1. In other words, you can traverse from index i to index j if the values at those positions share at least one common factor other than 1.

The problem asks you to determine if it's possible to create a path between every pair of indices in the array. Specifically, for any two indices i and j where i < j, there must exist some sequence of valid traversals that connects them (possibly through intermediate indices).

For example:

• If nums = [2, 4, 6], you can traverse between any pair of indices because all numbers share the factor 2
• If nums = [2, 3, 5], you cannot traverse between any indices because no two numbers share a common factor greater than 1

The function should return true if all pairs of indices are reachable from each other through some path of valid traversals, and false otherwise.

The solution uses a Union-Find (Disjoint Set Union) data structure to group indices that can be connected. It pre-computes prime factors for numbers and connects indices that share prime factors. If all indices end up in the same connected component, then all pairs are reachable from each other.

Intuition

The key insight is recognizing this as a graph connectivity problem. If we think of each index as a node, and draw an edge between two indices when their values share a common factor greater than 1, then the problem asks: "Is this graph fully connected?"

Initially, we might consider checking every pair of numbers to see if gcd(nums[i], nums[j]) > 1, but this would be inefficient for large arrays.

A crucial observation is that two numbers share a common factor greater than 1 if and only if they share at least one prime factor. For example, 6 and 15 both contain the prime factor 3, so gcd(6, 15) = 3 > 1.

This leads to a clever approach: instead of directly connecting indices whose values share factors, we can use prime factors as "bridges." If two numbers share a prime factor p, they're both connected to p, and therefore connected to each other through p.

Here's the transformation:

• Instead of checking if index i can connect to index j directly
• We connect index i to all prime factors of nums[i]
• We connect index j to all prime factors of nums[j]
• If they share any prime factor, they'll be in the same connected component

For example, if nums = [6, 10, 15]:

• Index 0 (value 6) connects to primes 2 and 3
• Index 1 (value 10) connects to primes 2 and 5
• Index 2 (value 15) connects to primes 3 and 5
• All indices end up connected through this prime factor network

Using Union-Find to track these connections efficiently determines if all indices form a single connected component. If they do, every pair of indices is reachable; otherwise, some pairs are isolated from each other.

Learn more about Union Find and Math patterns.

Solution Approach

The implementation consists of three main components:

1. Union-Find Data Structure

The UnionFind class implements a disjoint set union with path compression and union by size optimization:

• find(x): Finds the root of element x with path compression to flatten the tree structure
• union(a, b): Merges two sets containing a and b, using size-based merging to keep the tree balanced
• Each element starts as its own parent, and size tracks the size of each component

2. Prime Factorization Preprocessing

Before the main solution, the code pre-computes prime factors for all numbers up to mx = 100010:

for x in range(1, mx + 1):
    v = x
    i = 2
    while i <= v // i:  # Check divisors up to sqrt(v)
        if v % i == 0:
            p[x].append(i)  # Add prime factor i
            while v % i == 0:
                v //= i  # Remove all occurrences of i
        i += 1
    if v > 1:
        p[x].append(v)  # Add remaining prime factor

This creates a dictionary p where p[x] contains all prime factors of x.

3. Main Algorithm

The solution creates a Union-Find structure with n + m + 1 elements, where:

• Indices 0 to n-1 represent the array indices
• Indices n to n+m represent prime numbers (offset by n)

For each element nums[i]:

1. Look up its prime factors from the preprocessed dictionary
2. Union index i with each prime factor j (represented as j + n in the Union-Find)
3. This creates connections: if two indices share a prime factor, they'll be in the same component

Finally, check if all array indices belong to the same connected component:

return len(set(uf.find(i) for i in range(n))) == 1

If there's only one unique root among all array indices, then all pairs are reachable from each other.

Time Complexity: O(n × log(max(nums)) + n × α(n)) where α is the inverse Ackermann function Space Complexity: O(n + max(nums)) for the Union-Find structure and prime factor storage

Example Walkthrough

Let's walk through a small example with nums = [6, 10, 15] to illustrate how the solution works.

Step 1: Prime Factorization (Preprocessing) First, we identify the prime factors for each number:

• 6 = 2 × 3, so prime factors are [2, 3]
• 10 = 2 × 5, so prime factors are [2, 5]
• 15 = 3 × 5, so prime factors are [3, 5]

Step 2: Initialize Union-Find We create a Union-Find structure with space for:

• 3 array indices (0, 1, 2)
• Prime numbers we'll encounter (2, 3, 5)

Initially, each element is its own parent:

Array indices: [0] [1] [2]
Prime factors: [2] [3] [5]

Step 3: Connect Indices to Prime Factors

For index 0 (value 6):

• Union(0, 2): Connect index 0 with prime 2
• Union(0, 3): Connect index 0 with prime 3

Components: [0-2-3] [1] [5]

For index 1 (value 10):

• Union(1, 2): Connect index 1 with prime 2 (already connected to 0)
• Union(1, 5): Connect index 1 with prime 5

Components: [0-2-3-1-5]

For index 2 (value 15):

• Union(2, 3): Connect index 2 with prime 3 (already connected to 0 and 1)
• Union(2, 5): Connect index 2 with prime 5 (already connected)

Final: [0-2-3-1-5-2] (all in one component)

Step 4: Check Connectivity Find the root of each array index:

• find(0) = root
• find(1) = root (same as index 0)
• find(2) = root (same as index 0)

Since all three indices have the same root, they're all connected. This means:

• Index 0 can reach index 1 (through prime 2)
• Index 0 can reach index 2 (through prime 3)
• Index 1 can reach index 2 (through prime 5)

The function returns true because all pairs of indices are reachable.

Counter-example: If nums = [2, 3, 5] (all prime numbers):

• Index 0 connects only to prime 2
• Index 1 connects only to prime 3
• Index 2 connects only to prime 5
• No indices share prime factors, so they remain in separate components
• The function returns false

Solution Implementation

Time and Space Complexity

Time Complexity:

The algorithm consists of two main parts: preprocessing prime factors and the main solution.

1. Preprocessing prime factors: For each number from 1 to mx = 100010, we find all prime factors using trial division. For each number x, the inner loop runs up to √x, making the time complexity O(mx * √mx) = O(100010 * √100010) ≈ O(10^5 * 316) ≈ O(3.16 × 10^7).

2. Main solution:

   • Creating UnionFind: O(n + m) where n is the length of nums and m is the maximum value in nums
   • For each number in nums, we union it with all its prime factors. Each number has at most O(log m) prime factors. Each union operation with path compression has amortized complexity O(α(n + m)) where α is the inverse Ackermann function (practically constant)
   • The loop iterates through all n numbers, performing at most O(log m) unions each: O(n * log m * α(n + m))
   • Finding the root for all n elements: O(n * α(n + m))

Overall time complexity: O(mx * √mx + n * log m * α(n + m)) where the preprocessing dominates if done for all numbers up to mx. In practice, if we only precompute for numbers in the input, it would be O(n * √m + n * log m * α(n + m)).

Space Complexity:

1. Preprocessing storage: The dictionary p stores prime factors for numbers up to mx. Each number has at most O(log mx) prime factors, so the space is O(mx * log mx) ≈ O(10^5 * log 10^5) ≈ O(10^5 * 17).

2. UnionFind structure: Two arrays of size n + m + 1: O(n + m)

3. Set for checking connectivity: O(n)

Overall space complexity: O(mx * log mx + n + m) where the preprocessing storage dominates. If we only store prime factors for numbers in the input, it would be O(n * log m + n + m).

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

Common Pitfalls

1. Handling Single Element Arrays

A critical edge case that's easy to overlook is when the array contains only one element. By definition, if there's only one index, all pairs are trivially connected (there are no pairs to connect!). However, the algorithm might fail if the single element is 1.

Problem Example:

nums = [1]  # Should return true

When nums[0] = 1, it has no prime factors (since 1 has no prime divisors). This means no union operations occur, and the single index remains isolated. The check len(unique_roots) == 1 would still pass, but conceptually, we should handle this explicitly.

Solution:

def canTraverseAllPairs(self, nums: List[int]) -> bool:
    n = len(nums)
  
    # Handle single element case explicitly
    if n == 1:
        return True
  
    # If any element is 1 and n > 1, impossible to connect
    if 1 in nums:
        return False
  
    # Rest of the implementation...

2. Elements with Value 1

The number 1 has no prime factors (gcd(1, x) = 1 for all x ≠ 1). If the array contains 1 and has more than one element, it's impossible to connect all pairs since index containing 1 cannot be reached from any other index.

Problem Example:

nums = [2, 1, 3]  # Should return false

The index containing 1 will never be unioned with anything, creating an isolated component.

Solution:

def canTraverseAllPairs(self, nums: List[int]) -> bool:
    n = len(nums)
    if n == 1:
        return True
  
    # Check for 1 in arrays with multiple elements
    if any(num == 1 for num in nums):
        return False
  
    # Continue with Union-Find approach...

3. Memory Optimization for Large Prime Numbers

The current implementation allocates n + max(nums) + 1 nodes in the Union-Find structure. If the array contains a very large prime number (e.g., 99991), this wastes significant memory since most prime slots won't be used.

Problem Example:

nums = [2, 4, 99991]  # Allocates ~100000 nodes but uses very few

Solution: Use a mapping to assign consecutive IDs to unique primes:

def canTraverseAllPairs(self, nums: List[int]) -> bool:
    n = len(nums)
    if n == 1:
        return True
    if any(num == 1 for num in nums):
        return False
  
    # Map unique primes to consecutive IDs
    prime_to_id = {}
    prime_count = 0
  
    for value in nums:
        for prime in prime_factors[value]:
            if prime not in prime_to_id:
                prime_to_id[prime] = prime_count
                prime_count += 1
  
    # Create Union-Find with exact size needed
    union_find = UnionFind(n + prime_count)
  
    # Connect indices with their prime factors using mapped IDs
    for index, value in enumerate(nums):
        for prime in prime_factors[value]:
            prime_id = prime_to_id[prime]
            union_find.union(index, n + prime_id)
  
    unique_roots = set(union_find.find(i) for i in range(n))
    return len(unique_roots) == 1

4. Duplicate Values Optimization

If the array contains many duplicate values, the current approach redundantly processes the same prime factorizations multiple times.

Problem Example:

nums = [6, 6, 6, 6, 6]  # Processes prime factors of 6 five times

Solution: Group indices by value first to avoid redundant unions:

def canTraverseAllPairs(self, nums: List[int]) -> bool:
    n = len(nums)
    if n == 1:
        return True
    if any(num == 1 for num in nums):
        return False
  
    # Group indices by value
    value_to_indices = defaultdict(list)
    for i, num in enumerate(nums):
        value_to_indices[num].append(i)
  
    # Create Union-Find
    union_find = UnionFind(n + max(nums) + 1)
  
    # Process each unique value once
    for value, indices in value_to_indices.items():
        # Connect all indices with same value
        for i in range(1, len(indices)):
            union_find.union(indices[0], indices[i])
      
        # Connect first index with prime factors
        for prime in prime_factors[value]:
            union_find.union(indices[0], n + prime)
  
    unique_roots = set(union_find.find(i) for i in range(n))
    return len(unique_roots) == 1