Watch 10 video solutions for Graph Connectivity With Threshold, a hard level problem involving Array, Math, Union Find. This walkthrough by Shivam Patel has 1,394 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
We have n cities labeled from 1 to n. Two different cities with labels x and y are directly connected by a bidirectional road if and only if x and y share a common divisor strictly greater than some threshold. More formally, cities with labels x and y have a road between them if there exists an integer z such that all of the following are true:
x % z == 0,y % z == 0, andz > threshold.Given the two integers, n and threshold, and an array of queries, you must determine for each queries[i] = [ai, bi] if cities ai and bi are connected directly or indirectly. (i.e. there is some path between them).
Return an array answer, where answer.length == queries.length and answer[i] is true if for the ith query, there is a path between ai and bi, or answer[i] is false if there is no path.
Example 1:
Input: n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]] Output: [false,false,true] Explanation: The divisors for each number: 1: 1 2: 1, 2 3: 1, 3 4: 1, 2, 4 5: 1, 5 6: 1, 2, 3, 6 Using the underlined divisors above the threshold, only cities 3 and 6 share a common divisor, so they are the only ones directly connected. The result of each query: [1,4] 1 is not connected to 4 [2,5] 2 is not connected to 5 [3,6] 3 is connected to 6 through path 3--6
Example 2:
Input: n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]] Output: [true,true,true,true,true] Explanation: The divisors for each number are the same as the previous example. However, since the threshold is 0, all divisors can be used. Since all numbers share 1 as a divisor, all cities are connected.
Example 3:
Input: n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]] Output: [false,false,false,false,false] Explanation: Only cities 2 and 4 share a common divisor 2 which is strictly greater than the threshold 1, so they are the only ones directly connected. Please notice that there can be multiple queries for the same pair of nodes [x, y], and that the query [x, y] is equivalent to the query [y, x].
Constraints:
2 <= n <= 1040 <= threshold <= n1 <= queries.length <= 105queries[i].length == 21 <= ai, bi <= citiesai != biProblem Overview: You are given n nodes labeled from 1..n. Two nodes are connected if they share a common divisor strictly greater than a given threshold. For each query, you must determine whether two nodes belong to the same connected component.
Approach 1: Graph Construction + DFS Traversal (O(n log n + q) time, O(n + edges) space)
This approach explicitly builds a graph where nodes share an edge if their greatest common divisor is greater than threshold. Instead of checking every pair (which would be O(n²)), iterate through each integer d from threshold + 1 to n and connect all its multiples. Each multiple shares divisor d, which guarantees the constraint. After building the adjacency list, run DFS or BFS to mark connected components and answer queries by comparing component IDs. The technique relies on divisor iteration from number theory and standard graph traversal. This method is conceptually simple but can consume more memory due to explicit edge storage.
Approach 2: Union-Find with Optimized Factoring (O(n log n + q α(n)) time, O(n) space)
This is the optimal approach and avoids building the full graph. Use Union-Find (Disjoint Set Union) to merge nodes that share a divisor greater than threshold. Iterate d from threshold + 1 to n. For each d, union all multiples of d such as d, 2d, 3d.... Since these numbers share divisor d, they must belong to the same component. Path compression and union-by-rank make each operation nearly constant (α(n)). After preprocessing, each query becomes a simple check: find(u) == find(v). This avoids storing edges and scales well when n is large.
Recommended for interviews: Interviewers typically expect the Union-Find solution. Recognizing that numbers sharing a divisor form connected groups is the key insight. Starting with the graph interpretation demonstrates understanding of connectivity, but implementing the divisor iteration with DSU shows strong algorithmic thinking and familiarity with number-theoretic optimizations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph Construction + DFS | O(n log n + q) | O(n + edges) | Useful when you want an explicit graph structure for traversal or teaching connectivity concepts |
| Union-Find with Divisor Iteration | O(n log n + q α(n)) | O(n) | Best general solution for large inputs and typical interview expectations |