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 != biThe key observation in #1627 Graph Connectivity With Threshold is that two nodes are connected if they share a common divisor greater than the given threshold. Instead of checking every pair of nodes (which would be too slow), the optimal idea is to use the Union-Find (Disjoint Set Union) data structure to efficiently group numbers that share valid divisors.
Iterate through integers starting from threshold + 1 up to n. For each number, union it with its multiples (e.g., i, 2*i, 3*i...) since they all share the divisor i, which is guaranteed to be greater than the threshold. This effectively connects all nodes that share a valid common factor. After building these components, each query can be answered by simply checking whether the two nodes belong to the same set in the Union-Find structure.
This approach avoids explicit GCD checks for every pair and leverages number theory patterns, achieving near-linear performance with path compression and union by rank optimizations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Union-Find with multiples iteration | O(n log n + q α(n)) | O(n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
How to build the graph of the cities?
Connect city i with all its multiples 2*i, 3*i, ...
Answer the queries using union-find data structure.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems like this are common in FAANG-style interviews because they combine Union-Find with number theory insights. Interviewers often use it to test optimization skills and the ability to avoid brute-force pair comparisons.
Union-Find (Disjoint Set Union) is the most suitable data structure for this problem. It efficiently groups connected nodes and supports fast connectivity checks with path compression and union by rank.
The optimal approach uses the Union-Find (Disjoint Set Union) data structure. By iterating from threshold + 1 to n and unioning each number with its multiples, we connect nodes that share a common divisor greater than the threshold. Queries can then be answered quickly by checking if two nodes belong to the same component.
If a number i is greater than the threshold, all of its multiples share i as a common divisor. By unioning i with its multiples, we ensure all numbers sharing that divisor are placed in the same connected component.