Graph Connectivity With Threshold — LeetCode 1627 Python Solution
HardUnion FindArrayMathNumber Theory
- Problem
- #1627
- Pattern
- Union-Find
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
- Output
- [false,false,true]
- Explanation
- The divisors for each number:
Python solution
Python
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]Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n \times (\alpha(n) + q)) |
| Space | O(n) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1627. Graph Connectivity With Threshold is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Union Find.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
LeetCode 1998GCD Sort of an ArrayHardLeetCode 2709Greatest Common Divisor TraversalHardLeetCode 803Bricks Falling When HitHardLeetCode 1697Checking Existence of Edge Length Limited PathsHardLeetCode 2382Maximum Segment Sum After RemovalsHardLeetCode 2948Make Lexicographically Smallest Array by Swapping ElementsMedium
Frequently asked questions
- How hard is LeetCode 1627. Graph Connectivity With Threshold?
- LeetCode 1627. Graph Connectivity With Threshold is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1627. Graph Connectivity With Threshold?
- The Python solution on this page runs in O(n \times \log n \times (\alpha(n) + q)).
- What is the space complexity of LeetCode 1627. Graph Connectivity With Threshold?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1627. Graph Connectivity With Threshold cover?
- LeetCode 1627. Graph Connectivity With Threshold is tagged Union Find, Array, Math and Number Theory on LeetCode.