Checking Existence of Edge Length Limited Paths II — LeetCode 1724 Python Solution
HardLeetCode PremiumUnion FindGraphMinimum Spanning Tree
- Problem
- #1724
- Pattern
- Union-Find
- Reading time
- 7 min
- Source
- leetcode.com
The problem
An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes, and the graph may not be connected.
Example
- Input
- ["DistanceLimitedPathsExist", "query", "query", "query", "query"]
- Output
- [null, true, false, true, false]
- Explanation
- DistanceLimitedPathsExist distanceLimitedPathsExist = new DistanceLimitedPathsExist(6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]);
Python solution
Python
class PersistentUnionFind:
def __init__(self, n):
self.rank = [0] * n
self.p = list(range(n))
self.version = [inf] * n
def find(self, x, t=inf):
if self.p[x] == x or self.version[x] >= t:
return x
return self.find(self.p[x], t)
def union(self, a, b, t):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.rank[pa] > self.rank[pb]:
self.version[pb] = t
self.p[pb] = pa
else:
self.version[pa] = t
self.p[pa] = pb
if self.rank[pa] == self.rank[pb]:
self.rank[pb] += 1
return True
class DistanceLimitedPathsExist:
def __init__(self, n: int, edgeList: List[List[int]]):
self.puf = PersistentUnionFind(n)
edgeList.sort(key=lambda x: x[2])
for u, v, dis in edgeList:
self.puf.union(u, v, dis)
def query(self, p: int, q: int, limit: int) -> bool:
return self.puf.find(p, limit) == self.puf.find(q, limit)Complexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 1724. Checking Existence of Edge Length Limited Paths II is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
LeetCode 1697Checking Existence of Edge Length Limited PathsHardLeetCode 1489Find Critical and Pseudo-Critical Edges in Minimum Spanning TreeHardLeetCode 1584Min Cost to Connect All PointsMediumLeetCode 399Evaluate DivisionMediumLeetCode 547Number of ProvincesMediumLeetCode 684Redundant ConnectionMedium
Frequently asked questions
- How hard is LeetCode 1724. Checking Existence of Edge Length Limited Paths II?
- LeetCode 1724. Checking Existence of Edge Length Limited Paths II is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1724. Checking Existence of Edge Length Limited Paths II?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1724. Checking Existence of Edge Length Limited Paths II?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1724. Checking Existence of Edge Length Limited Paths II cover?
- LeetCode 1724. Checking Existence of Edge Length Limited Paths II is tagged Union Find, Graph and Minimum Spanning Tree on LeetCode.
- Is LeetCode 1724. Checking Existence of Edge Length Limited Paths II a premium problem?
- Yes. LeetCode 1724. Checking Existence of Edge Length Limited Paths II is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.