Checking Existence of Edge Length Limited Paths

Hard
954.

Checking Existence of Edge Length Limited Paths

Checking Existence of Edge Length Limited Paths is a hard coding problem on arrays, sorting and graph, asked in Amazon, Google and Microsoft interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edgeList
 * @param {number[][]} queries
 * @return {number[]}
 */
var distanceLimitedPathsExist = function(n, edgeList, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.

Hints for Checking Existence of Edge Length Limited Paths

  1. Hint 1

    Answering each query with its own search is far too slow.

  2. Hint 2

    Answer the queries offline, in increasing order of their limit.

  3. 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

  1. Sort the edges ascending by distance.
  2. Sort the query indices by limit, keeping the original positions for the output.
  3. For each query in that order, union in all remaining edges with distance < limit.
  4. 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

Java

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