Greatest Common Divisor Traversal

Hard · Graphs · Explanation and code example

Sieve of Eratosthenes + BFS

How it works

BFS provides an iterative alternative to DFS for checking graph connectivity. We build the same graph structure connecting indices to prime nodes, then use a queue to explore all reachable nodes starting from index 0.

Steps

  1. Handle edge cases: single element returns true; any value of 1 returns false.
  2. Build a sieve array for smallest prime factors.
  3. Construct an adjacency list connecting indices to their prime factor nodes (offset by N).
  4. Initialize a queue with index 0 and a visited set.
  5. Process nodes via BFS, adding unvisited neighbors to the queue.
  6. Return true if all indices (0 to N-1) were visited.

Complexity

  • Time complexity: O(m + n log m)
  • Space complexity: O(n + m)

Where n is the size of the array nums and m is the maximum value in the array.

Things to watch for

Not Handling the Value 1 as a Special Case

The number 1 has no prime factors greater than 1, so it cannot share a common factor with any other number. If the array contains 1 and has more than one element, the answer is always false. Failing to check for this edge case will cause incorrect results or infinite loops during factorization.

Forgetting the Single Element Case

When the array has only one element, all pairs are trivially traversable (there are no pairs to check). This should return true regardless of the value. Missing this base case leads to incorrect behavior, especially if your factorization or union-find logic assumes at least two elements.

Incorrect Prime Factorization

When factorizing numbers, you must completely divide out each prime factor before moving to the next. A common bug is incrementing the factor without fully removing it, causing duplicate unions or missed factors. Use a while loop to divide out each prime completely: while (num % prime == 0) num /= prime.

Off-by-One Errors in Virtual Prime Nodes

When using Union-Find with virtual nodes for primes (offset by N), ensure consistent indexing. Array indices run from 0 to N-1, while prime nodes are at positions N + prime. Mixing up these offsets or forgetting to add N when accessing prime nodes causes incorrect unions and false connectivity results.

Memory Issues with Large Prime Values

When the maximum value in the array is large (up to 10^5 or 10^6), allocating arrays sized by the maximum value can consume significant memory. Ensure your sieve and Union-Find structures are appropriately sized as N + MAX + 1 to accommodate both indices and virtual prime nodes without out-of-bounds errors.

Python code example

from typing import List
from collections import defaultdict, deque

class Solution:
    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

        MAX = max(nums)
        sieve = [0] * (MAX + 1)
        p = 2
        while p * p <= MAX:
            if sieve[p] == 0:
                for composite in range(p * p, MAX + 1, p):
                    sieve[composite] = p
            p += 1

        adj = defaultdict(list)
        for i in range(N):
            num = nums[i]
            if sieve[num] == 0:  # num is prime
                adj[i].append(N + num)
                adj[N + num].append(i)
                continue

            while num > 1:
                prime = sieve[num] if sieve[num] != 0 else num
                adj[i].append(N + prime)
                adj[N + prime].append(i)
                while num % prime == 0:
                    num //= prime

        visited = set()
        queue = deque([0])
        visited.add(0)
        while queue:
            node = queue.popleft()
            for nei in adj[node]:
                if nei not in visited:
                    visited.add(nei)
                    queue.append(nei)

        for i in range(N):
            if i not in visited:
                return False
        return True

C++ code example

class Solution {
public:
    bool canTraverseAllPairs(vector<int>& nums) {
        int N = nums.size();
        if (N == 1) return true;
        if (find(nums.begin(), nums.end(), 1) != nums.end()) return false;

        int MAX = *max_element(nums.begin(), nums.end());
        vector<int> sieve(MAX + 1, 0);
        int p = 2;
        while (p * p <= MAX) {
            if (sieve[p] == 0) {
                for (int composite = p * p; composite <= MAX; composite += p) {
                    sieve[composite] = p;
                }
            }
            p++;
        }

        unordered_map<int, vector<int>> adj;
        for (int i = 0; i < N; i++) {
            int num = nums[i];
            if (sieve[num] == 0) { // num is prime
                adj[i].push_back(N + num);
                adj[N + num].push_back(i);
                continue;
            }

            while (num > 1) {
                int prime = (sieve[num] != 0) ? sieve[num] : num;
                adj[i].push_back(N + prime);
                adj[N + prime].push_back(i);
                while (num % prime == 0) {
                    num /= prime;
                }
            }
        }

        unordered_set<int> visited;
        queue<int> q;
        q.push(0);
        visited.insert(0);

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            for (int& nei : adj[node]) {
                if (visited.find(nei) == visited.end()) {
                    visited.insert(nei);
                    q.push(nei);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            if (visited.find(i) == visited.end()) {
                return false;
            }
        }
        return true;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations