Graph Connectivity With Threshold - Solution & Explanation
Problem Statement
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 != bi
Approach Overview
Problem 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 1: Union-Find with Optimized Factoring
This approach uses a union-find (or disjoint set union, DSU) data structure to determine connectivity between cities based on common divisors greater than the threshold. Starting from threshold + 1 to n, cities are grouped into sets if they share a common divisor greater than the given threshold. Each query is then simply a matter of checking if two nodes are in the same set.
The UnionFind class implements the Disjoint Set Union structure with path compression and union by rank, which helps maintain efficient connectivity checks. The core of the solution pre-joins cities based on common divisors greater than the threshold and then simply checks if the specified pairs in queries are connected.
Complexity
Time Complexity: O(n log* n + q) where n is the number of cities and q is the number of queries. Due to the near-constant time nature of union-find operations, the time is efficient.
Space Complexity: O(n) due to the storage of parent and rank arrays in union-find.
Approach 2: Graph Representation and DFS
This approach involves representing the connectivity between cities as a graph and then using graph traversal techniques such as Depth-First Search (DFS) to determine if there's a path between cities for each query. Cities sharing a common divisor greater than the threshold form edges in the graph.
This Java solution first creates an adjacency list to represent the graph based on city connectivity (divisors greater than threshold) and uses a DFS traversal to determine path existence between cities for each query.
Code
Java
JavaScript
Complexity
Time Complexity: O(n^2 + q * V) where V is the number of vertices visited during each DFS, typically much less than n; the worst-case time complexity being high for dense graphs.
Space Complexity: O(n^2) for storing the adjacency list.
Approach 3: Union-Find
We can enumerate z and its multiples, and use union-find to connect them. In this way, for each query [a, b], we only need to determine whether a and b are in the same connected component.
The time complexity is O(n times log n times (\alpha(n) + q)), and the space complexity is O(n). Here, n and q are the number of nodes and queries, respectively, and \alpha is the inverse function of the Ackermann function.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Union-Find with Optimized Factoring | Time Complexity: O(n log* n + q) where n is the number of cities and q is the number of queries. Due to the near-constant time nature of union-find operations, the time is efficient. |
| Graph Representation and DFS | Time Complexity: O(n^2 + q * V) where V is the number of vertices visited during each DFS, typically much less than n; the worst-case time complexity being high for dense graphs. |
| Union-Find | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Leetcode 1627 (Hard) Graph Connectivity With Threshold: Simple C++ Solution with [Union Find]. • Shivam Patel • 1,409 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Graph Connectivity With Threshold easy or hard?
Graph Connectivity With Threshold Python/Java solution
How to solve Graph Connectivity With Threshold in O(n log n)?
What is the best approach for Graph Connectivity With Threshold?
Is Graph Connectivity With Threshold asked at Google/Amazon/Meta?
What data structure is used in Graph Connectivity With Threshold?
What is the time complexity of Graph Connectivity With Threshold?
Ready to solve this problem?
Practice Graph Connectivity With Threshold with our built-in code editor and test cases.
Practice on FleetCode