Greatest Common Divisor Traversal

Greatest Common Divisor Traversal: the approach in brief

The problem

Implement Solution.canTraverseAllPairs, which receives an integer array nums. Treat each array position as a vertex; positions remain distinct even when their values are equal.

Pattern

Greatest Common Divisor Traversal is a Graph Traversal Patterns (DFS & BFS) problem, in the Union-Find (Disjoint Set Union - DSU) subpattern. The pattern covers dFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Approach outline

1. Think of positions as vertices in an undirected graph, with an edge whenever the two corresponding values have a common factor greater than 1.
2. Connecting every pair directly would be too expensive. Instead, use prime factors as intermediate connection points.
3. A disjoint-set union structure can merge all values that share a prime factor and then test whether all positions have the same representative.

Complexity

The reference solution runs in O(M log log M + n log M · α(n + M)), where M is the maximum value in nums; equivalently, factoring and union operations are near-linear in the input size for the given bounds. time and O(n + M) space.