Graph Connectivity With Threshold
HardPrompt
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--6Example 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
Approaches
3 approaches with complexity analysis and trade-offs.
This is the most naive approach. First, an explicit graph is constructed by checking every pair of cities for a direct connection. An adjacency list is used to store the graph. Then, for each query, a graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) is run to check for a path between the two cities.
Algorithm
1. Create an adjacency listadjof sizen+1to represent the graph.2. For each integerifrom1ton:a. For each integerjfromi + 1ton:i. Iteratezfromthreshold + 1toi.ii. Ifi % z == 0andj % z == 0, an edge exists. Addjtoadj[i]anditoadj[j], then break the inner loop.3. Initialize an empty listanswerto store query results.4. For each query[a, b]inqueries:a. Perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting fromato check ifbis reachable.b. Addtruetoanswerif a path is found, otherwise addfalse.5. Return theanswerlist.
Walkthrough
This method separates the problem into two distinct phases: graph building and path finding.
Graph Building:
- Create an adjacency list,
adj, to represent the graph, whereadj[i]stores the neighbors of cityi. - Iterate through all pairs of cities
(i, j)with1 <= i < j <= n. - For each pair, check if they share a common divisor
z > threshold. This can be done by iteratingzfromthreshold + 1toi. - If such a
zis found, add an edge betweeniandjin the adjacency list (i.e., addjtoadj[i]anditoadj[j]).
Query Processing:
- For each query
[a, b], perform a traversal (e.g., BFS) starting from citya. - Use a
visitedarray to keep track of visited nodes during the traversal. - If city
bis reached during the traversal, the cities are connected. - If the traversal completes without reaching
b, they are not connected.
This approach is highly inefficient because it rebuilds the path-finding work for every single query.
import java.util.*; class Solution { public List<Boolean> areConnected(int n, int threshold, int[][] queries) { // 1. Graph Building List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); } if (threshold == 0) { List<Boolean> allConnected = new ArrayList<>(); for (int i = 0; i < queries.length; i++) allConnected.add(true); return allConnected; } for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { for (int z = threshold + 1; z <= i; z++) { if (i % z == 0 && j % z == 0) { adj.get(i).add(j); adj.get(j).add(i); break; } } } } // 2. Query Processing List<Boolean> result = new ArrayList<>(); for (int[] query : queries) { result.add(hasPath(query[0], query[1], n, adj)); } return result; } private boolean hasPath(int start, int end, int n, List<List<Integer>> adj) { if (start == end) return true; Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[n + 1]; queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int curr = queue.poll(); if (curr == end) return true; for (int neighbor : adj.get(curr)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } return false; }}Complexity
Time
O(n^3 + Q * (n + E)), where `n` is the number of cities, `Q` is the number of queries, and `E` is the number of edges. In the worst case, `E` can be `O(n^2)`. The graph construction takes `O(n^3)` and each of the `Q` queries takes `O(n+E)`. This is prohibitively slow.
Space
O(n + E), where E is the number of edges. In the worst case, E can be O(n^2), so the space complexity is O(n^2).
Trade-offs
Pros
Very straightforward and easy to understand for those familiar with basic graph algorithms.
Cons
Extremely inefficient due to the O(n^3) graph construction time.
Query processing is also slow, as it repeats traversal work for each query.
The space complexity for the adjacency list can be large, up to O(n^2).
Guaranteed to result in Time Limit Exceeded for the given constraints.
This approach iterates through all possible pairs of cities (i, j). For each pair, it checks if they are directly connected by finding a common divisor z greater than the threshold. If they are, it uses a Disjoint Set Union (DSU) data structure to merge their components. After checking all pairs, the DSU structure contains all connectivity information, allowing for fast query processing.
Algorithm
1. Create a Disjoint Set Union (DSU) data structure forn+1elements.2. For each integerifrom1ton:a. For each integerjfromi + 1ton:i. Check if there exists a common divisorz > thresholdforiandj.ii. If such azexists, performunion(i, j)and break the inner check.3. Initialize an empty listanswer.4. For each query[a, b]inqueries:a. Check iffind(a)is equal tofind(b).b. Add the result to theanswerlist.5. Return theanswerlist.
Walkthrough
This method improves upon a pure brute-force approach by using a DSU to efficiently handle the transitive nature of connectivity. Instead of running a graph traversal for each query, we pre-compute all connected components.
The algorithm is as follows:
- Initialize a DSU structure for
n+1elements. - Iterate through every pair of distinct cities
(i, j)where1 <= i < j <= n. - For each pair, determine if they are directly connected. This is done by checking for a common divisor
z > threshold. A simple way to do this is to iteratezfromthreshold + 1toi(sincei < j). - If a
zis found such thati % z == 0andj % z == 0, it means citiesiandjare directly connected. We then performunion(i, j)and can stop checking other divisors for this pair. - After iterating through all pairs, the DSU is fully built.
- Process each query
[a, b]by checking iffind(a) == find(b).
The main drawback is the O(n^2) pairs to check, and for each pair, we might do up to O(n) work, leading to a high time complexity for the graph construction phase.
import java.util.*; class DSU { private int[] parent; private int[] size; public DSU(int n) { parent = new int[n + 1]; size = new int[n + 1]; for (int i = 0; i <= n; i++) { parent[i] = i; size[i] = 1; } } public int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } public void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) { if (size[rootI] < size[rootJ]) { parent[rootI] = rootJ; size[rootJ] += size[rootI]; } else { parent[rootJ] = rootI; size[rootI] += size[rootJ]; } } }} class Solution { public List<Boolean> areConnected(int n, int threshold, int[][] queries) { if (threshold == 0) { List<Boolean> allConnected = new ArrayList<>(); for (int i = 0; i < queries.length; i++) allConnected.add(true); return allConnected; } DSU dsu = new DSU(n); for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { for (int z = threshold + 1; z <= i; z++) { if (i % z == 0 && j % z == 0) { dsu.union(i, j); break; } } } } List<Boolean> result = new ArrayList<>(); for (int[] query : queries) { result.add(dsu.find(query[0]) == dsu.find(query[1])); } return result; }}Complexity
Time
O(n^3 * α(n) + Q * α(n)). The construction phase iterates through O(n^2) pairs, and for each pair, it may check up to O(n) divisors. Each union operation takes O(α(n)) time. The query part is fast, but the construction is the bottleneck.
Space
O(n) to store the parent and size arrays for the DSU data structure.
Trade-offs
Pros
Conceptually simpler than the most optimal approach.
Efficiently handles queries once the DSU structure is built, with nearly constant time per query.
Cons
The graph construction phase is very slow, with a time complexity of O(n^3) in the worst case.
Will result in Time Limit Exceeded for the given constraints.
This approach avoids building an explicit graph or checking all pairs of cities. Instead, it iterates through all possible common divisors z greater than the threshold. For each such z, it identifies all its multiples up to n and unifies them into a single connected component using a Disjoint Set Union (DSU) data structure. This is efficient because the total number of union operations is related to the harmonic series, resulting in an O(n log n) complexity for building the connectivity information.
Algorithm
1. Create a Disjoint Set Union (DSU) data structure forn+1elements.2. For each integerzfromthreshold + 1ton:a. For each multiplemofz(i.e.,2z, 3z, ...) that is less than or equal ton:i. Performunion(z, m)to connect cityzand citym.3. Initialize an empty listanswerto store results.4. For each query[a, b]inqueries:a. Check iffind(a)is equal tofind(b).b. Add the result (trueorfalse) to theanswerlist.5. Return theanswerlist.
Walkthrough
The core idea is to realize that if two numbers a and b are multiples of z, they are connected (if z > threshold). By extension, all multiples of z are mutually connected and belong to the same component.
We can use a Union-Find (or DSU) data structure to efficiently manage these connected components. The DSU will have n+1 elements, representing cities 1 to n.
The algorithm proceeds as follows:
- Initialize a DSU structure for
n+1elements, where each city is in its own set. - Iterate through each integer
zfromthreshold + 1up ton. Thiszwill be our potential common divisor. - For each
z, iterate through its multiples:2*z, 3*z, 4*z, ...up ton. - For each multiple
m = k*z, we know thatzis a common divisor ofzandm. Sincez > threshold, citieszandmare connected. We perform aunion(z, m)operation. This effectively groups all multiples ofzinto the same set. - After iterating through all possible
zvalues, the DSU structure will accurately represent the connectivity of all cities. - Finally, process the
queries. For each query[a, b], we check ifaandbare in the same set by comparing their roots:find(a) == find(b). If they are, the cities are connected; otherwise, they are not.
This method is much faster than pairwise checks because the total number of operations in the nested loops is sum_{z=threshold+1 to n} (n/z), which is bounded by n * sum_{z=1 to n} (1/z) ≈ n * log(n).
import java.util.*; class DSU { private int[] parent; private int[] size; public DSU(int n) { parent = new int[n + 1]; size = new int[n + 1]; for (int i = 0; i <= n; i++) { parent[i] = i; size[i] = 1; } } public int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } public void union(int i, int j) { int rootI = find(i); int rootJ = find(j); if (rootI != rootJ) { if (size[rootI] < size[rootJ]) { parent[rootI] = rootJ; size[rootJ] += size[rootI]; } else { parent[rootJ] = rootI; size[rootI] += size[rootJ]; } } }} class Solution { public List<Boolean> areConnected(int n, int threshold, int[][] queries) { if (threshold == 0) { List<Boolean> allConnected = new ArrayList<>(); for (int i = 0; i < queries.length; i++) allConnected.add(true); return allConnected; } DSU dsu = new DSU(n); for (int z = threshold + 1; z <= n; z++) { for (int m = 2 * z; m <= n; m += z) { dsu.union(z, m); } } List<Boolean> result = new ArrayList<>(); for (int[] query : queries) { int u = query[0]; int v = query[1]; result.add(dsu.find(u) == dsu.find(v)); } return result; }}Complexity
Time
O(n * log(n) * α(n) + Q * α(n)), where `n` is the number of cities, `Q` is the number of queries, and `α(n)` is the inverse Ackermann function (a very slowly growing function, effectively constant). The `n * log(n)` part comes from iterating through divisors and their multiples (related to the harmonic series sum), and each union/find operation takes `α(n)` time.
Space
O(n) to store the parent and size arrays for the DSU data structure.
Trade-offs
Pros
Very efficient for building the connectivity information, with a time complexity of O(n log n).
Query processing is nearly constant time per query, making it suitable for a large number of queries.
Space complexity is linear, O(n), which is optimal.
Cons
Requires understanding of the Disjoint Set Union data structure.
The logic is less direct than a brute-force check, involving a shift in perspective from checking city pairs to checking common divisors.
Solutions
Solution
class UnionFind { private int [] p ; private int [] size ; public UnionFind ( int n ) { p = new int [ n ]; size = new int [ n ]; for ( int i = 0 ; i < n ; ++ i ) { p [ i ] = i ; size [ i ] = 1 ; } } public int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } public boolean union ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } } class Solution { public List < Boolean > areConnected ( int n , int threshold , int [][] queries ) { UnionFind uf = new UnionFind ( n + 1 ); for ( int a = threshold + 1 ; a <= n ; ++ a ) { for ( int b = a + a ; b <= n ; b += a ) { uf . union ( a , b ); } } List < Boolean > ans = new ArrayList <>(); for ( var q : queries ) { ans . add ( uf . find ( q [ 0 ]) == uf . find ( q [ 1 ])); } return ans ; } }class UnionFind { public: UnionFind ( int n ) { p = vector < int > ( n ); size = vector < int > ( n , 1 ); iota ( p . begin (), p . end (), 0 ); } bool unite ( int a , int b ) { int pa = find ( a ), pb = find ( b ); if ( pa == pb ) { return false ; } if ( size [ pa ] > size [ pb ]) { p [ pb ] = pa ; size [ pa ] += size [ pb ]; } else { p [ pa ] = pb ; size [ pb ] += size [ pa ]; } return true ; } int find ( int x ) { if ( p [ x ] != x ) { p [ x ] = find ( p [ x ]); } return p [ x ]; } private: vector < int > p , size ; }; class Solution { public: vector < bool > areConnected ( int n , int threshold , vector < vector < int >>& queries ) { UnionFind uf ( n + 1 ); for ( int a = threshold + 1 ; a <= n ; ++ a ) { for ( int b = a + a ; b <= n ; b += a ) { uf . unite ( a , b ); } } vector < bool > ans ; for ( auto & q : queries ) { ans . push_back ( uf . find ( q [ 0 ]) == uf . find ( q [ 1 ])); } return ans ; } };class UnionFind : def __init__ ( self , n ): self . p = list ( range ( n )) self . size = [ 1 ] * n def find ( self , x ): if self . p [ x ] != x : self . p [ x ] = self . find ( self . p [ x ]) return self . p [ x ] def union ( self , a , b ): pa , pb = self . find ( a ), self . find ( b ) if pa == pb : return False if self . size [ pa ] > self . size [ pb ]: self . p [ pb ] = pa self . size [ pa ] += self . size [ pb ] else : self . p [ pa ] = pb self . size [ pb ] += self . size [ pa ] return True class Solution : def areConnected ( self , n : int , threshold : int , queries : List [ List [ int ]] ) -> List [ bool ]: uf = UnionFind ( n + 1 ) for a in range ( threshold + 1 , n + 1 ): for b in range ( a + a , n + 1 , a ): uf . union ( a , b ) return [ uf . find ( a ) == uf . find ( b ) for a , b in queries ]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.