1627. Graph Connectivity With Threshold LeetCode Solution
In this guide, you will get 1627. Graph Connectivity With Threshold LeetCode Solution with the best time and space complexity. The solution to Graph Connectivity With Threshold problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Graph Connectivity With Threshold solution in C++
- Graph Connectivity With Threshold solution in Java
- Graph Connectivity With Threshold solution in Python
- Additional Resources
Problem Statement of Graph Connectivity With Threshold
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, and
z > 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 <= 104
0 <= threshold <= n
1 <= queries.length <= 105
queries[i].length == 2
1 <= ai, bi <= cities
ai != bi
Complexity Analysis
- Time Complexity: O(n\log^* n)
- Space Complexity: O(n)
1627. Graph Connectivity With Threshold LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), rank(n) {
iota(id.begin(), id.end(), 0);
}
bool unionByRank(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return false;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
return true;
}
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
private:
vector<int> id;
vector<int> rank;
};
class Solution {
public:
vector<bool> areConnected(int n, int threshold,
vector<vector<int>>& queries) {
vector<bool> ans;
UnionFind uf(n + 1);
for (int z = threshold + 1; z <= n; ++z)
for (int x = z * 2; x <= n; x += z)
uf.unionByRank(z, x);
for (const vector<int>& query : queries) {
const int a = query[0];
const int b = query[1];
ans.push_back(uf.find(a) == uf.find(b));
}
return ans;
}
};
/* code provided by PROGIEZ */1627. Graph Connectivity With Threshold LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public boolean unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return false;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
return true;
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
private int[] id;
private int[] rank;
}
class Solution {
public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
List<Boolean> ans = new ArrayList<>();
UnionFind uf = new UnionFind(n + 1);
for (int z = threshold + 1; z <= n; ++z)
for (int x = z * 2; x <= n; x += z)
uf.unionByRank(z, x);
for (int[] query : queries) {
final int a = query[0];
final int b = query[1];
ans.add(uf.find(a) == uf.find(b));
}
return ans;
}
}
// code provided by PROGIEZ1627. Graph Connectivity With Threshold LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
def unionByRank(self, u: int, v: int) -> bool:
i = self.find(u)
j = self.find(v)
if i == j:
return False
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
return True
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
class Solution:
def areConnected(
self,
n: int,
threshold: int,
queries: list[list[int]],
) -> list[bool]:
uf = UnionFind(n + 1)
for z in range(threshold + 1, n + 1):
for x in range(z * 2, n + 1, z):
uf.unionByRank(z, x)
return [uf.find(a) == uf.find(b) for a, b in queries]
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.