Watch 10 video solutions for Greatest Common Divisor Traversal, a hard level problem involving Array, Math, Union Find. This walkthrough by NeetCodeIO has 14,037 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums, and you are allowed to traverse between its indices. You can traverse between index i and index j, i != j, if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.
Your task is to determine if for every pair of indices i and j in nums, where i < j, there exists a sequence of traversals that can take us from i to j.
Return true if it is possible to traverse between all such pairs of indices, or false otherwise.
Example 1:
Input: nums = [2,3,6] Output: true Explanation: In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2). To go from index 0 to index 1, we can use the sequence of traversals 0 -> 2 -> 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1. To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1.
Example 2:
Input: nums = [3,9,5] Output: false Explanation: No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.
Example 3:
Input: nums = [4,3,12,8] Output: true Explanation: There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105Problem Overview: You receive an array of integers. You can move between two indices if the gcd(nums[i], nums[j]) > 1. The task is to determine whether every index can be reached from any starting index, meaning the implicit graph formed by these gcd relationships is fully connected.
Approach 1: Graph Traversal by Adjacency List (O(n² log M) time, O(n²) space)
Treat every number as a node in a graph. Compare every pair of values and compute gcd(nums[i], nums[j]). If the result is greater than 1, add an edge between the two indices in an adjacency list. After building the graph, run DFS or BFS to check whether all nodes are reachable from index 0. This approach directly models the graph but performs a gcd calculation for every pair, which becomes expensive for large arrays. It works well for small inputs or when building intuition around graph traversal.
Approach 2: Graph Traversal with Union-Find and Prime Factors (O(n log M) time, O(n + M) space)
Instead of comparing every pair, connect numbers through their prime factors. Factorize each value and track which indices share the same factor. If two numbers contain a common prime factor, union their indices using a Union-Find structure. A hash map from factor → index allows quick unions as factors repeat. This effectively builds the connectivity of the graph without enumerating all edges. Prime factorization takes roughly O(log M) per number using trial division or a smallest-prime-factor sieve from number theory. After processing the entire array, check whether all indices belong to the same set.
The key insight: if two numbers share any prime factor, their gcd is greater than 1, so they belong in the same connected component. Chaining these unions across shared factors builds the full connectivity of the array.
Recommended for interviews: The Union-Find with prime factorization approach. The adjacency-list solution shows you understand the graph model but fails to scale because of the O(n²) pair checks. Interviewers expect the optimized approach that reduces the problem to factor connectivity and merges components using disjoint sets.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Adjacency List + DFS/BFS | O(n² log M) | O(n²) | Small arrays or when demonstrating the direct graph interpretation |
| Union-Find with Prime Factorization | O(n log M) | O(n + M) | Large inputs and interview settings where optimal connectivity detection is required |