The "Checking Existence of Edge Length Limited Paths II" problem presents you with an undirected, weighted graph with n nodes labeled from 0 to n - 1. The graph is defined by an array edgeList of edges, where each edge is represented as [u, v, w], indicating an undirected edge between nodes u and v with weight w.
You are also given a list of queries, where each query is of the form [p, q, limit]. For each query, you must determine if there exists a path between nodes p and q in the graph such that all edges along the path have weights strictly less than limit.
The goal is to efficiently answer multiple such queries. The constraints are:
When first approaching this problem, it's tempting to consider running a graph traversal (like BFS or DFS) for each query, only following edges with weights less than the given limit. However, since there can be up to 105 queries, this brute-force approach would be far too slow.
The challenge is to answer each query much faster than running a traversal every time. This suggests preprocessing the graph or queries in a way that lets us answer each query quickly. Since all queries are independent, and the only thing that changes is the limit, we can try to process the queries in a way that reuses work across similar queries.
The key realization is that, for a given limit, the set of edges with weights less than limit forms a subgraph. If we can efficiently determine whether two nodes are connected in this subgraph, we can answer the query quickly.
This leads us to use the Union-Find (Disjoint Set Union) data structure, which can efficiently keep track of connected components as we "add" edges in increasing order of weight.
We will use an offline processing strategy, where we sort both the edgeList and the queries by edge weight and limit, respectively. This allows us to process all queries in increasing order of their limit and efficiently build the connectivity information as we go.
edgeList by edge weight in ascending order. This helps us add edges to our Union-Find structure in order of increasing weight.
limit values, sort them by limit. To remember their original order, store the original index with each query.
n nodes. This lets us efficiently merge and check connectivity.
[p, q, limit], add to the Union-Find all edges with weight less than limit (i.e., process edges in order, and "activate" them as soon as their weight is less than the current limit).p and q are connected in the Union-Find.Why Union-Find? Because it allows us to merge connected components efficiently (almost O(1) with path compression and union by rank), and to check if two nodes are connected in near-constant time.
Suppose:
n = 5edgeList = [[0,1,2], [1,2,4], [2,3,6], [3,4,8]]queries = [[0,4,5], [0,2,3], [1,3,7]][[0,1,2], [1,2,4], [2,3,6], [3,4,8]]
Brute-force approach:
This is efficient enough for the largest constraints.
The core insight is to process queries and edges in order of increasing weight/limit, using Union-Find to dynamically maintain connectivity. This avoids redundant traversals and leverages efficient data structures to answer each query in near-constant time. The approach is elegant because it transforms a seemingly per-query graph traversal into a single sweep over the sorted data, making it scalable to large graphs and query sets.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0]*n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
xr, yr = self.find(x), self.find(y)
if xr == yr:
return
if self.rank[xr] < self.rank[yr]:
self.parent[xr] = yr
else:
self.parent[yr] = xr
if self.rank[xr] == self.rank[yr]:
self.rank[xr] += 1
class Solution:
def distanceLimitedPathsExist(self, n, edgeList, queries):
# Attach original indices to queries
queries = [(p, q, limit, i) for i, (p, q, limit) in enumerate(queries)]
queries.sort(key=lambda x: x[2])
edgeList.sort(key=lambda x: x[2])
uf = UnionFind(n)
res = [False] * len(queries)
edge_idx = 0
for p, q, limit, idx in queries:
# Add all edges with weight < limit
while edge_idx < len(edgeList) and edgeList[edge_idx][2] < limit:
u, v, w = edgeList[edge_idx]
uf.union(u, v)
edge_idx += 1
if uf.find(p) == uf.find(q):
res[idx] = True
return res
class UnionFind {
public:
vector<int> parent, rank;
UnionFind(int n) : parent(n), rank(n, 0) {
for (int i = 0; i < n; ++i) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
int xr = find(x), yr = find(y);
if (xr == yr) return;
if (rank[xr] < rank[yr]) parent[xr] = yr;
else {
parent[yr] = xr;
if (rank[xr] == rank[yr]) rank[xr]++;
}
}
};
class Solution {
public:
vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
int qlen = queries.size();
vector<tuple<int, int, int, int>> q;
for (int i = 0; i < qlen; ++i) {
q.push_back(make_tuple(queries[i][0], queries[i][1], queries[i][2], i));
}
sort(edgeList.begin(), edgeList.end(), [](const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
});
sort(q.begin(), q.end(), [](const tuple<int,int,int,int>& a, const tuple<int,int,int,int>& b) {
return get<2>(a) < get<2>(b);
});
UnionFind uf(n);
vector<bool> res(qlen, false);
int edge_idx = 0, elen = edgeList.size();
for (auto& tup : q) {
int p = get<0>(tup), qq = get<1>(tup), limit = get<2>(tup), idx = get<3>(tup);
while (edge_idx < elen && edgeList[edge_idx][2] < limit) {
uf.unite(edgeList[edge_idx][0], edgeList[edge_idx][1]);
edge_idx++;
}
if (uf.find(p) == uf.find(qq)) res[idx] = true;
}
return res;
}
};
class UnionFind {
int[] parent, rank;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i) parent[i] = i;
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
int xr = find(x), yr = find(y);
if (xr == yr) return;
if (rank[xr] < rank[yr]) parent[xr] = yr;
else {
parent[yr] = xr;
if (rank[xr] == rank[yr]) rank[xr]++;
}
}
}
class Solution {
public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
int qlen = queries.length;
int[][] q = new int[qlen][4];
for (int i = 0; i < qlen; ++i) {
q[i][0] = queries[i][0];
q[i][1] = queries[i][1];
q[i][2] = queries[i][2];
q[i][3] = i;
}
Arrays.sort(edgeList, (a, b) -> a[2] - b[2]);
Arrays.sort(q, (a, b) -> a[2] - b[2]);
UnionFind uf = new UnionFind(n);
boolean[] res = new boolean[qlen];
int edge_idx = 0;
for (int[] query : q) {
int p = query[0], qq = query[1], limit = query[2], idx = query[3];
while (edge_idx < edgeList.length && edgeList[edge_idx][2] < limit) {
uf.union(edgeList[edge_idx][0], edgeList[edge_idx][1]);
edge_idx++;
}
if (uf.find(p) == uf.find(qq)) res[idx] = true;
}
return res;
}
}
class UnionFind {
constructor(n) {
this.parent = Array(n).fill(0).map((_, i) => i);
this.rank = Array(n).fill(0);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]);
}
return this.parent[x];
}
union(x, y) {
let xr = this.find(x), yr = this.find(y);
if (xr === yr) return;
if (this.rank[xr] < this.rank[yr]) this.parent[xr] = yr;
else {
this.parent[yr] = xr;
if (this.rank[xr] === this.rank[yr]) this.rank[xr]++;
}
}
}
var distanceLimitedPathsExist = function(n, edgeList, queries) {
let q = queries.map((arr, i) => [...arr, i]);
q.sort((a, b) => a[2] - b[2]);
edgeList.sort((a, b) => a[2] - b[2]);
let uf = new UnionFind(n);
let res = Array(queries.length).fill(false);
let edge_idx = 0;
for (let [p, qv, limit, idx] of q) {
while (edge_idx < edgeList.length && edgeList[edge_idx][2] < limit) {
uf.union(edgeList[edge_idx][0], edgeList[edge_idx][1]);
edge_idx++;
}
if (uf.find(p) === uf.find(qv)) res[idx] = true;
}
return res;
};