Checking Existence of Edge Length Limited Paths II solution and explanation
Google
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.
Implement the DistanceLimitedPathsExist class:
DistanceLimitedPathsExist(int n, int[][] edgeList)Initializes the class with an undirected graph.boolean query(int p, int q, int limit)Returnstrueif there exists a path fromptoqsuch that each edge on the path has a distance strictly less thanlimit, and otherwisefalse.
Example 1:
Input ["DistanceLimitedPathsExist", "query", "query", "query", "query"] [[6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]], [2, 3, 2], [1, 3, 3], [2, 0, 3], [0, 5, 6]] 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]]); distanceLimitedPathsExist.query(2, 3, 2); // return true. There is an edge from 2 to 3 of distance 1, which is less than 2. distanceLimitedPathsExist.query(1, 3, 3); // return false. There is no way to go from 1 to 3 with distances strictly less than 3. distanceLimitedPathsExist.query(2, 0, 3); // return true. There is a way to go from 2 to 0 with distance < 3: travel from 2 to 3 to 0. distanceLimitedPathsExist.query(0, 5, 6); // return false. There are no paths from 0 to 5.
Constraints:
2 <= n <= 1040 <= edgeList.length <= 104edgeList[i].length == 30 <= ui, vi, p, q <= n-1ui != vip != q1 <= disi, limit <= 109- At most
104calls will be made toquery.
Approach overview
Problem Overview: You are given a weighted undirected graph and must repeatedly answer queries of the form (p, q, limit). Each query asks whether a path exists between nodes p and q where every edge weight is strictly less than limit. Queries happen after preprocessing, so the solution must answer them quickly.
Approach 1: Per-Query Graph Search (BFS/DFS) (Time: O(Q * (V + E)), Space: O(V))
For every query, run a BFS or DFS starting from node p. Only traverse edges whose weight is less than limit. If node q is reached, the answer is true. This approach directly models the constraint but repeats the same work for each query. With many queries or dense graphs, repeatedly scanning edges becomes expensive.
Approach 2: Offline Queries with Union Find (Time: O((E + Q) log E), Space: O(V))
If all queries are known in advance, sort edges by weight and sort queries by their limit. Incrementally add edges into a Union-Find structure while the edge weight is smaller than the current query limit. After inserting all valid edges, check whether p and q belong to the same component. This technique works well for the single-batch version of the problem but does not handle dynamic queries efficiently because queries must be processed in sorted order.
Approach 3: Minimum Spanning Tree + Binary Lifting (Time: O(E log E + V log V + Q log V), Space: O(V log V))
The key insight comes from the properties of a Minimum Spanning Tree. For any two nodes, the path between them in the MST minimizes the maximum edge weight among all possible paths in the original graph. Build the MST using Kruskal's algorithm and a Union-Find structure. Then preprocess the tree with binary lifting (LCA) while storing the maximum edge weight from each node to its ancestors.
For a query (p, q, limit), compute the maximum edge weight along the MST path between p and q. If that maximum is less than limit, a valid path exists in the original graph. Each query becomes an LCA computation with maximum-edge tracking, which runs in O(log V). The heavy work happens during preprocessing, making queries extremely fast.
Recommended for interviews: The MST + LCA approach is the expected solution. It shows you understand MST bottleneck properties and how to combine them with fast ancestor queries. Mentioning the per-query BFS demonstrates baseline reasoning, while the MST-based preprocessing demonstrates the optimization interviewers look for in hard graph problems.
Solution
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)class PersistentUnionFind {
private final int inf = 1 << 30;
private int[] rank;
private int[] parent;
private int[] version;
public PersistentUnionFind(int n) {
rank = new int[n];
parent = new int[n];
version = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
version[i] = inf;
}
}
public int find(int x, int t) {
if (parent[x] == x || version[x] >= t) {
return x;
}
return find(parent[x], t);
}
public boolean union(int a, int b, int t) {
int pa = find(a, inf);
int pb = find(b, inf);
if (pa == pb) {
return false;
}
if (rank[pa] > rank[pb]) {
version[pb] = t;
parent[pb] = pa;
} else {
version[pa] = t;
parent[pa] = pb;
if (rank[pa] == rank[pb]) {
rank[pb]++;
}
}
return true;
}
}
public class DistanceLimitedPathsExist {
private PersistentUnionFind puf;
public DistanceLimitedPathsExist(int n, int[][] edgeList) {
puf = new PersistentUnionFind(n);
Arrays.sort(edgeList, (a, b) -> a[2] - b[2]);
for (var e : edgeList) {
puf.union(e[0], e[1], e[2]);
}
}
public boolean query(int p, int q, int limit) {
return puf.find(p, limit) == puf.find(q, limit);
}
}
/**
* Your DistanceLimitedPathsExist object will be instantiated and called as such:
* DistanceLimitedPathsExist obj = new DistanceLimitedPathsExist(n, edgeList);
* boolean param_1 = obj.query(p,q,limit);
*/class PersistentUnionFind {
private:
vector<int> rank;
vector<int> parent;
vector<int> version;
public:
PersistentUnionFind(int n)
: rank(n, 0)
, parent(n)
, version(n, INT_MAX) {
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x, int t) {
if (parent[x] == x || version[x] >= t) {
return x;
}
return find(parent[x], t);
}
bool unionSet(int a, int b, int t) {
int pa = find(a, INT_MAX);
int pb = find(b, INT_MAX);
if (pa == pb) {
return false;
}
if (rank[pa] > rank[pb]) {
version[pb] = t;
parent[pb] = pa;
} else {
version[pa] = t;
parent[pa] = pb;
if (rank[pa] == rank[pb]) {
rank[pb]++;
}
}
return true;
}
};
class DistanceLimitedPathsExist {
private:
PersistentUnionFind puf;
public:
DistanceLimitedPathsExist(int n, vector<vector<int>>& edgeList)
: puf(n) {
sort(edgeList.begin(), edgeList.end(),
[](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
for (const auto& edge : edgeList) {
puf.unionSet(edge[0], edge[1], edge[2]);
}
}
bool query(int p, int q, int limit) {
return puf.find(p, limit) == puf.find(q, limit);
}
};
/**
* Your DistanceLimitedPathsExist object will be instantiated and called as such:
* DistanceLimitedPathsExist* obj = new DistanceLimitedPathsExist(n, edgeList);
* bool param_1 = obj->query(p,q,limit);
*/class PersistentUnionFind {
private rank: number[];
private parent: number[];
private version: number[];
constructor(n: number) {
this.rank = Array(n).fill(0);
this.parent = Array.from({ length: n }, (_, i) => i);
this.version = Array(n).fill(Infinity);
}
find(x: number, t: number): number {
if (this.parent[x] === x || this.version[x] >= t) {
return x;
}
return this.find(this.parent[x], t);
}
union(a: number, b: number, t: number): boolean {
const pa = this.find(a, Infinity);
const pb = this.find(b, Infinity);
if (pa === pb) {
return false;
}
if (this.rank[pa] > this.rank[pb]) {
this.version[pb] = t;
this.parent[pb] = pa;
} else {
this.version[pa] = t;
this.parent[pa] = pb;
if (this.rank[pa] === this.rank[pb]) {
this.rank[pb]++;
}
}
return true;
}
}
class DistanceLimitedPathsExist {
private puf: PersistentUnionFind;
constructor(n: number, edgeList: number[][]) {
this.puf = new PersistentUnionFind(n);
edgeList.sort((a, b) => a[2] - b[2]);
for (const [u, v, dis] of edgeList) {
this.puf.union(u, v, dis);
}
}
query(p: number, q: number, limit: number): boolean {
return this.puf.find(p, limit) === this.puf.find(q, limit);
}
}
/**
* Your DistanceLimitedPathsExist object will be instantiated and called as such:
* var obj = new DistanceLimitedPathsExist(n, edgeList)
* var param_1 = obj.query(p,q,limit)
*/type PersistentUnionFind struct {
rank []int
parent []int
version []int
}
func NewPersistentUnionFind(n int) *PersistentUnionFind {
rank := make([]int, n)
parent := make([]int, n)
version := make([]int, n)
for i := 0; i < n; i++ {
parent[i] = i
}
return &PersistentUnionFind{
rank: rank,
parent: parent,
version: version,
}
}
func (uf *PersistentUnionFind) find(x int, t int) int {
if uf.parent[x] == x || uf.version[x] >= t {
return x
}
return uf.find(uf.parent[x], t)
}
func (uf *PersistentUnionFind) union(a, b, t int) bool {
pa := uf.find(a, int(^uint(0)>>1))
pb := uf.find(b, int(^uint(0)>>1))
if pa == pb {
return false
}
if uf.rank[pa] > uf.rank[pb] {
uf.version[pb] = t
uf.parent[pb] = pa
} else {
uf.version[pa] = t
uf.parent[pa] = pb
if uf.rank[pa] == uf.rank[pb] {
uf.rank[pb]++
}
}
return true
}
type DistanceLimitedPathsExist struct {
puf *PersistentUnionFind
}
func Constructor(n int, edgeList [][]int) DistanceLimitedPathsExist {
sort.Slice(edgeList, func(i, j int) bool {
return edgeList[i][2] < edgeList[j][2]
})
puf := NewPersistentUnionFind(n)
for _, edge := range edgeList {
puf.union(edge[0], edge[1], edge[2])
}
return DistanceLimitedPathsExist{
puf: puf,
}
}
func (dle *DistanceLimitedPathsExist) Query(p, q, limit int) bool {
return dle.puf.find(p, limit) == dle.puf.find(q, limit)
}
/**
* Your DistanceLimitedPathsExist object will be instantiated and called as such:
* obj := Constructor(n, edgeList);
* param_1 := obj.Query(p,q,limit);
*/Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Per-query BFS/DFS | O(Q * (V + E)) | O(V) | Small graphs or very few queries |
| Offline Queries with Union-Find | O((E + Q) log E) | O(V) | When all queries are known beforehand and can be sorted |
| MST + LCA (Binary Lifting) | O(E log E + V log V + Q log V) | O(V log V) | Best choice for many online queries after preprocessing |
Frequently asked questions
Is Checking Existence of Edge Length Limited Paths II easy or hard?
LeetCode classifies this problem as Hard. The challenge is recognizing the MST bottleneck property and combining it with LCA preprocessing to support fast repeated queries. Implementing Union-Find and binary lifting correctly is required for an optimal solution.
Checking Existence of Edge Length Limited Paths II Python/Java solution
Most implementations build the MST using Union-Find, then preprocess parent and maximum-edge tables for binary lifting. The query method climbs the tree to the LCA while tracking the maximum edge weight. The same algorithm translates cleanly across Python, Java, C++, Go, and TypeScript.
What is the best approach for Checking Existence of Edge Length Limited Paths II?
The optimal approach builds a Minimum Spanning Tree using Kruskal's algorithm and then preprocesses the tree using binary lifting for Lowest Common Ancestor queries. For each query, compute the maximum edge weight along the path between the two nodes in the MST. If that value is less than the limit, a valid path exists. This gives O(log n) query time after preprocessing.
Is Checking Existence of Edge Length Limited Paths II asked at Google/Amazon/Meta?
Problems combining Union-Find, Minimum Spanning Trees, and LCA preprocessing frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of graph connectivity, MST properties, and fast query processing after preprocessing.
What data structure is used in Checking Existence of Edge Length Limited Paths II?
The solution uses several core structures: Union-Find for building the Minimum Spanning Tree with Kruskal's algorithm, adjacency lists to store the MST, and binary lifting tables for Lowest Common Ancestor queries. These structures allow efficient preprocessing and fast query responses.
What is the time complexity of Checking Existence of Edge Length Limited Paths II?
The optimized solution runs in O(E log E + V log V + Q log V). Building the MST requires sorting edges, which takes O(E log E). LCA preprocessing takes O(V log V), and each query is answered in O(log V) time by checking the maximum edge weight along the MST path.
How to solve Checking Existence of Edge Length Limited Paths II in O(log n) per query?
First construct a Minimum Spanning Tree from the graph. Then preprocess the tree using binary lifting to compute Lowest Common Ancestors while storing the maximum edge weight to each ancestor. Each query checks the maximum edge weight on the path between two nodes in O(log n). If the maximum weight is less than the limit, the path satisfies the constraint.