Checking Existence of Edge Length Limited Paths — Solution
Checking Existence of Edge Length Limited Paths solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Checking Existence of Edge Length Limited Paths is a hard coding problem on arrays, sorting and graph, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Graph, Union Find
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
An undirected graph on n nodes is given by edgeList[i] = [u, v, distance]; there may be several edges between the same pair, and some nodes may be unreachable from others.
For each queries[j] = [p, q, limit], answer 1 if there is a path from p to q using only edges of distance strictly less than limit, and 0 otherwise.
Example 1
Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [0,1]
Explanation: The first query's limit of 2 excludes the only 0–1 edge; the second reaches 2 via `0 → 1 → 2`.
Example 2
Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output: [1,0]
Example 3
Input: n = 2, edgeList = [[0,1,1]], queries = [[0,1,1]]
Output: [0]
Explanation: The limit is strict, so a distance of exactly 1 does not qualify.
Constraints
2 <= n <= 10^51 <= edgeList.length, queries.length <= 10^5edgeList[i].length == 3queries[j].length == 30 <= u, v, p, q <= n - 1u != vp != q1 <= distance, limit <= 10^9There may be multiple edges between two nodes.
Hints for Checking Existence of Edge Length Limited Paths
Hint 1
Answering each query with its own search is far too slow.
Hint 2
Answer the queries offline, in increasing order of their limit.
Hint 3
Then a union-find only ever gains edges, never loses them.
How to solve Checking Existence of Edge Length Limited Paths
Sort the edges by distance and the queries by limit, then sweep. Before answering a query, add every edge shorter than its limit to a union-find; the answer is whether the two nodes now share a root.
Approach
- Sort the edges ascending by distance.
- Sort the query indices by limit, keeping the original positions for the output.
- For each query in that order, union in all remaining edges with distance
< limit. - Record whether the two endpoints share a root, writing into the original position.
Why it works
Processing queries in increasing limit means the edge pointer only ever moves forward, so every edge is added at most once across all queries — that is what makes the whole sweep near-linear. It also means the union-find is never asked to remove an edge, which it cannot do.
Complexity
- Time —
O((m + q) log(m + q) · α(n)) - Space —
O(n + q)
Pitfalls
- The limit is strict: an edge of distance exactly
limitmust not be used. - Answers must be written back in the queries' original order.
- Multiple edges between the same pair are harmless — the union simply has no effect the second time.
Reference solution
Python
from typing import List
def distanceLimitedPathsExist(n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[int]:
parent = list(range(n))
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
es = sorted(edgeList, key=lambda e: e[2])
order = sorted(range(len(queries)), key=lambda i: queries[i][2])
out = [0] * len(queries)
e = 0
for idx in order:
p, q, limit = queries[idx]
while e < len(es) and es[e][2] < limit:
ra, rb = find(es[e][0]), find(es[e][1])
if ra != rb:
parent[rb] = ra
e += 1
out[idx] = 1 if find(p) == find(q) else 0
return outJava
private static int[] elParent;
private static int elFind(int x) {
while (elParent[x] != x) {
elParent[x] = elParent[elParent[x]];
x = elParent[x];
}
return x;
}
public static int[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
elParent = new int[n];
for (int i = 0; i < n; i++) elParent[i] = i;
int[][] es = edgeList.clone();
Arrays.sort(es, (a, b) -> Integer.compare(a[2], b[2]));
Integer[] order = new Integer[queries.length];
for (int i = 0; i < queries.length; i++) order[i] = i;
Arrays.sort(order, (a, b) -> Integer.compare(queries[a][2], queries[b][2]));
int[] out = new int[queries.length];
int e = 0;
for (int idx : order) {
int limit = queries[idx][2];
while (e < es.length && es[e][2] < limit) {
int ra = elFind(es[e][0]), rb = elFind(es[e][1]);
if (ra != rb) elParent[rb] = ra;
e++;
}
out[idx] = elFind(queries[idx][0]) == elFind(queries[idx][1]) ? 1 : 0;
}
return out;
}C++
vector<int> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
vector<int> parent(n);
for (int i = 0; i < n; i++) parent[i] = i;
function<int(int)> find = [&](int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
vector<vector<int>> es = edgeList;
sort(es.begin(), es.end(), [](const vector<int>& a, const vector<int>& b) { return a[2] < b[2]; });
vector<int> order(queries.size());
for (size_t i = 0; i < order.size(); i++) order[i] = (int) i;
sort(order.begin(), order.end(), [&](int a, int b) { return queries[a][2] < queries[b][2]; });
vector<int> out(queries.size(), 0);
size_t e = 0;
for (int idx : order) {
int limit = queries[idx][2];
while (e < es.size() && es[e][2] < limit) {
int ra = find(es[e][0]), rb = find(es[e][1]);
if (ra != rb) parent[rb] = ra;
e++;
}
out[idx] = find(queries[idx][0]) == find(queries[idx][1]) ? 1 : 0;
}
return out;
}JavaScript
var distanceLimitedPathsExist = function(n, edgeList, queries) {
var i;
var parent = [];
for (i = 0; i < n; i++) parent.push(i);
var find = function(x) {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
var es = edgeList.slice();
es.sort(function(a, b) { return a[2] - b[2]; });
var order = [];
for (i = 0; i < queries.length; i++) order.push(i);
order.sort(function(a, b) { return queries[a][2] - queries[b][2]; });
var out = [];
for (i = 0; i < queries.length; i++) out.push(0);
var e = 0;
for (var k = 0; k < order.length; k++) {
var idx = order[k];
var limit = queries[idx][2];
while (e < es.length && es[e][2] < limit) {
var ra = find(es[e][0]), rb = find(es[e][1]);
if (ra !== rb) parent[rb] = ra;
e++;
}
out[idx] = find(queries[idx][0]) === find(queries[idx][1]) ? 1 : 0;
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms