Checking Existence of Edge Length Limited Paths — Hard Problem & Solution

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…

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^5
1 <= edgeList.length, queries.length <= 10^5
edgeList[i].length == 3
queries[j].length == 3
0 <= u, v, p, q <= n - 1
u != v
p != q
1 <= distance, limit <= 10^9
There may be multiple edges between two nodes.

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 limit must 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue