1627. Graph Connectivity With Threshold
Problem Description
In this problem, we have a total of n
cities, and these cities are labeled from 1
to n
. The roads between these cities are not built in a typical manner based on location or distance but rather on a numerical criterion related to the city labels. Two cities, x
and y
, are directly linked by a road if their labels have a common factor (divisor) greater than a given threshold
. In other words, there exists an integer z
greater than threshold
such that both x
and y
are divisible by z
.
We are given a list of queries
, each containing a pair of cities [ai, bi]
. For each query, the question is to determine whether there is a path between city ai
and city bi
. This path can be direct (the cities have a common factor greater than the threshold) or indirect (there is a sequence of roads connecting the two cities, possibly passing through other cities).
The goal is to return an array, indicating for each query whether a path exists (true
) or does not exist (false
).
Intuition
To solve this problem, we use an algorithmic technique known as Union-Find, which efficiently tracks elements grouped into disjoint sets and can quickly determine whether any two elements are in the same set. This approach is particularly useful for problems related to networking, connectivity, and clustering.
The intuition behind the solution lies in the observation that if two cities have a common divisor greater than the threshold
, we can consider them to be in the same group or "connected component". Our task is to group all cities into connected components based on the given criterion. Once we have established these components, we can answer each query by simply checking if the two cities belong to the same component.
Since directly computing common divisors for every city pair would be computationally intensive, we can instead iterate over each possible divisor z
that is greater than the threshold
. For each z
, we connect all cities that are multiples of z
. In effect, we are building up the connectivity graph by progressively linking cities that have a common factor. This way, after processing all z
, each connected component represents a set of cities that are all interlinked through shared divisors.
When processing the queries, we use the Union-Find data structure to quickly determine whether any two cities a
and b
are in the same connected component. With the connectivity graph prepared via Union-Find, each query only takes constant time to answer.
The overall solution is efficient because it systematically builds the connectivity relationship using divisors greater than the threshold and then leverages the Union-Find structure for fast query resolution.
Learn more about Union Find and Math patterns.
Solution Approach
The solution approach involves the use of the Union-Find algorithm. The main objective of using Union-Find here is to group the cities into disjoint sets where each set represents a cluster of cities that are interconnected. Below is the step-by-step walkthrough of the implementation:
-
Initialization of Union-Find: We first create a Union-Find data structure (represented by the
UnionFind
class). Each city is initially represented as a separate set (or component), as indicated by theself.p
list that stores the parent for each city. Theself.size
list keeps track of the size of each set. -
Building the connectivity graph: We iterate through every possible integer
z
greater than thethreshold
. For each such integer, we loop through the multiples ofz
(a
), starting fromthreshold + 1
(since any number less than or equal to the threshold shouldn't be connected according to the problem statement). For each multiplea
, we find other multiplesb
(whereb
starts froma + a
to avoid redundant pairs and countinga
itself) and union the sets thata
andb
belong to. Theunion
function is responsible for merging sets, ensuring that ifa
is connected tob
, all cities connected toa
are now considered connected tob
as well. -
Answering the queries: Once the connectivity graph is established, we answer the queries. For each query
[ai, bi]
, we check if citiesai
andbi
are in the same set by comparing their ultimate parents in the Union-Find structure. If their parents are the same, they share a connection, directly or indirectly, and hence we returntrue
. Otherwise, we returnfalse
.
The strength of the solution is due to the way Union-Find efficiently combines sets and checks for connectivity. The find
function is optimized with path compression, making subsequent searches for the same element faster. The union
function also performs union by size (sometimes known as union by rank), ensuring that the tree representing a set remains as flat as possible to minimize the depth of searches.
Correctly utilized, this results in a solution that is highly efficient in terms of both time and space complexity, enabling it to solve even large-scale connectivity problems with many elements and connections.
The process of finding common divisors and union operations ensures that all cities that could possibly share a path based on the rules of the problem are placed in the same connected component, which allows for efficient query responses regarding their connectivity.
This approach works since we deal with the numbers (city labels) themselves and the commonalities between these numbers in the context of their divisors, enabling a numerical and algebraic solution to what could otherwise be approached as a graph connectivity problem.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a simple scenario where we have n = 6
cities, labeled from 1
to 6
, and we set our threshold
to 2
. Therefore, two cities will be connected if they share a common factor (divisor) greater than 2
.
Now, let's process our city connectivity using the Union-Find algorithm according to the Solution Approach described above:
-
Initialization of Union-Find: We have an array of
n
city slots representing each city as a separate 'parent', simulating the initial separate sets for each city. For simplicity, this can be represented asparents = [1, 2, 3, 4, 5, 6]
, where the index represents the city, and the value at each index represents its current set parent. -
Building the connectivity graph: We iterate through integers greater than
2
, i.e.,z = 3, 4, 5, 6, ...
. We start connecting cities based on these multiples.- For
z = 3
, we find cities3
and6
as multiples. We perform the union operation for cities3
and6
. - For
z = 4
,4
is in its own set, so no operation is needed here since there are no other multiples less or equal to6
. - We continue for
z = 5
andz = 6
, but since no other multiples exist within our city range, no further union operations are performed.
After the iteration, we might end up with parents array resembling something like
parents = [1, 2, 3, 4, 5, 3]
, which implies city6
now has3
as its parent, meaning they belong to the same set. - For
-
Answering the queries: Suppose we have queries
[[1, 4], [4, 5], [3, 6]]
that ask if there's a connection between the pairs of cities:- For
[1, 4]
, they do not have a common parent, so they are not connected (result:false
). - For
[4, 5]
, they do not have a common parent either, so they are not connected (result:false
). - For
[3, 6]
, they both share a common parent of3
(because we united them earlier based on being multiples of3
), so they are connected (result:true
).
- For
By utilizing Union-Find with these steps, we efficiently grouped cities into subsets based on their shared factors above the threshold and swiftly answered queries about their connectivity. The resulting array of answers for our queries case would be [false, false, true]
.
Solution Implementation
1from typing import List
2
3
4class UnionFind:
5 def __init__(self, size: int):
6 # Initialize the parents to point to themselves and set the size of each set to 1
7 self.parent = list(range(size))
8 self.set_size = [1] * size
9
10 def find(self, node: int) -> int:
11 # Find the root of the node with path compression
12 if self.parent[node] != node:
13 self.parent[node] = self.find(self.parent[node])
14 return self.parent[node]
15
16 def union(self, node1: int, node2: int) -> bool:
17 # Union the sets containing node1 and node2
18 root1, root2 = self.find(node1), self.find(node2)
19
20 # If both nodes have the same root, they are already connected
21 if root1 == root2:
22 return False
23
24 # Attach the smaller set to the root of the larger set
25 if self.set_size[root1] > self.set_size[root2]:
26 self.parent[root2] = root1
27 self.set_size[root1] += self.set_size[root2]
28 else:
29 self.parent[root1] = root2
30 self.set_size[root2] += self.set_size[root1]
31
32 # The union was successful
33 return True
34
35
36class Solution:
37 def are_connected(
38 self, nodes_count: int, threshold: int, queries: List[List[int]]
39 ) -> List[bool]:
40 # Initialize UnionFind with one extra space for 1-based indexing
41 uf = UnionFind(nodes_count + 1)
42
43 # Only consider numbers greater than the threshold for union
44 for a in range(threshold + 1, nodes_count + 1):
45 # Union multiples of a
46 for b in range(2 * a, nodes_count + 1, a):
47 uf.union(a, b)
48
49 # Process each query to check if two nodes are connected
50 return [uf.find(node1) == uf.find(node2) for node1, node2 in queries]
51
52
53# You can test the functionality by creating an instance of Solution and calling
54# the are_connected method with appropriate arguments.
55
1class UnionFind {
2 private int[] parent; // Parent array to store the representative element for each set
3 private int[] size; // Array to store the size of each set
4
5 public UnionFind(int n) {
6 parent = new int[n];
7 size = new int[n];
8 // Initialize each element to be a self-parent (own set) with size 1
9 for (int i = 0; i < n; ++i) {
10 parent[i] = i;
11 size[i] = 1;
12 }
13 }
14
15 // Find the representative of the set to which 'x' belongs
16 public int find(int x) {
17 if (parent[x] != x) {
18 // Path compression, pointing the current element directly to the representative
19 parent[x] = find(parent[x]);
20 }
21 return parent[x];
22 }
23
24 // Merge the sets containing 'a' and 'b'
25 public boolean union(int a, int b) {
26 int parentA = find(a), parentB = find(b);
27
28 // Return false if both elements are already in the same set
29 if (parentA == parentB) {
30 return false;
31 }
32
33 // Weighed union: attach the smaller tree to the root of the larger tree
34 if (size[parentA] > size[parentB]) {
35 parent[parentB] = parentA;
36 size[parentA] += size[parentB];
37 } else {
38 parent[parentA] = parentB;
39 size[parentB] += size[parentA];
40 }
41 return true; // Return true as the union was successful
42 }
43}
44
45class Solution {
46 public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
47 UnionFind uf = new UnionFind(n + 1); // Create a union-find for 'n' elements
48
49 // Start from 'threshold + 1' and connect all multiples
50 for (int a = threshold + 1; a <= n; ++a) {
51 for (int b = a + a; b <= n; b += a) {
52 uf.union(a, b); // Union sets containing 'a' and 'b'
53 }
54 }
55
56 List<Boolean> ans = new ArrayList<>(); // List to store the answer for each query
57 for (int[] query : queries) {
58 // Check if 'query[0]' and 'query[1]' have the same representative
59 ans.add(uf.find(query[0]) == uf.find(query[1]));
60 }
61
62 return ans; // Return the list containing query results
63 }
64}
65
1#include <vector>
2#include <numeric>
3
4class UnionFind {
5public:
6 // Constructor initializes two vectors, one for storing parent references, and another for size of each set
7 UnionFind(int n) {
8 parents = std::vector<int>(n);
9 sizes = std::vector<int>(n, 1);
10
11 // Fill the parents vector so that each element is initially its own parent
12 std::iota(parents.begin(), parents.end(), 0);
13 }
14
15 // Unite two sets; if they are already connected return false, otherwise unite and return true
16 bool unite(int a, int b) {
17 int parentA = find(a), parentB = find(b);
18
19 // Check if both elements have the same parent
20 if (parentA == parentB) {
21 return false;
22 }
23
24 // Union by size: attach the smaller tree to the root of the larger tree
25 if (sizes[parentA] > sizes[parentB]) {
26 parents[parentB] = parentA;
27 sizes[parentA] += sizes[parentB];
28 } else {
29 parents[parentA] = parentB;
30 sizes[parentB] += sizes[parentA];
31 }
32
33 return true;
34 }
35
36 // Find the root parent of a given element, with path compression
37 int find(int x) {
38 // Path compression: Make each looked-up element point to the root directly
39 if (parents[x] != x) {
40 parents[x] = find(parents[x]);
41 }
42
43 return parents[x];
44 }
45
46private:
47 std::vector<int> parents; // Vector to store the parent of each element
48 std::vector<int> sizes; // Vector to store the size of each set (only valid for root elements)
49};
50
51class Solution {
52public:
53 // Method to determine if the given queries are connected considering a certain threshold
54 std::vector<bool> areConnected(int n, int threshold, std::vector<std::vector<int>>& queries) {
55 UnionFind uf(n + 1);
56
57 // Connect nodes which are multiples of each number greater than the threshold
58 for (int a = threshold + 1; a <= n; ++a) {
59 for (int b = 2 * a; b <= n; b += a) {
60 uf.unite(a, b);
61 }
62 }
63
64 std::vector<bool> answers; // This will hold the final answers to queries
65
66 // For each query, check if the two queried numbers are connected
67 for (auto& query : queries) {
68 bool isConnected = uf.find(query[0]) == uf.find(query[1]);
69 answers.push_back(isConnected);
70 }
71
72 return answers;
73 }
74};
75
1// Global variables representing the disjoint set data structure
2const parent: number[] = [];
3const setSize: number[] = [];
4
5// Initializes the disjoint set data structure with `n` elements
6function initializeUnionFind(n: number): void {
7 for (let i = 0; i <= n; i++) {
8 parent[i] = i;
9 setSize[i] = 1;
10 }
11}
12
13// Returns the root of the set that element `x` belongs to
14function find(x: number): number {
15 if (parent[x] !== x) {
16 parent[x] = find(parent[x]); // Path compression
17 }
18 return parent[x];
19}
20
21// Merges the sets to which elements `a` and `b` belong, and
22// returns true if a merge happened, false if already connected
23function union(a: number, b: number): boolean {
24 let rootA = find(a);
25 let rootB = find(b);
26
27 if (rootA === rootB) {
28 return false; // Already in the same set
29 }
30
31 // Union by size: attach the smaller tree to the root of the larger tree
32 if (setSize[rootA] > setSize[rootB]) {
33 parent[rootB] = rootA;
34 setSize[rootA] += setSize[rootB];
35 } else {
36 parent[rootA] = rootB;
37 setSize[rootB] += setSize[rootA];
38 }
39 return true;
40}
41
42// Determines if nodes `a` and `b` are connected for each query in `queries`
43function areConnected(n: number, threshold: number, queries: number[][]): boolean[] {
44 initializeUnionFind(n); // Initialize for n+1 elements (0 through n inclusive)
45
46 // Connect all multiples of each number starting from `threshold + 1` through `n`
47 for (let a = threshold + 1; a <= n; ++a) {
48 for (let b = a * 2; b <= n; b += a) {
49 union(a, b); // Union multiples of `a`
50 }
51 }
52
53 // For each query, check if the elements are connected
54 return queries.map(([a, b]) => find(a) === find(b));
55}
56
Time and Space Complexity
The time complexity of the UnionFind
operations is O(α(n))
, where α
is the inverse Ackermann function, which is nearly constant for all practical values of n
. The initialization of the UnionFind
instance is O(n)
since it requires initializing two lists of size n
.
In the areConnected
function, we start iterating through each number a
from threshold + 1
to n
. For each a
, we iterate through its multiples b
, starting from a + a
to n
with a step of a
. There would be approximately n / a
multiples of a
to consider, and since the union
operation is performed for each multiple, the complexity for iterating through multiples of a
would be O((n / a) * α(n))
. Summing this over all numbers from threshold + 1
to n
, the complexity approximates Σ(n / a)
from a = threshold + 1
to n
, which is roughly O(n * log(n))
, as this is a harmonic series which can be bounded by the logarithm.
When considering the queries, each query involves two find
operations, leading to a complexity of O(q * α(n))
, where q
is the number of queries.
The overall time complexity, which combines the complexity of initializing the UnionFind
, iterating over the numbers and their multiples, and processing the queries, is O(n + n * log(n) * α(n) + q * α(n))
, simplifying to O(n * log(n) * α(n) + q * α(n))
.
The space complexity is O(n)
due to the storage requirements of the UnionFind
data structure, which needs to store the parent and size for each of the n
nodes.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?
Recommended Readings
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.