Checking Existence of Edge Length Limited Paths II

Checking Existence of Edge Length Limited Paths II - 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) Returns true if there exists a path from p to q such that each edge on the path has a distance strictly less than limit, and otherwise false.

Input & Output

Example 1 — Basic Graph

$ Input: n = 4, edges = [[0,1,3],[1,2,1],[2,3,1]], queries = [[0,3,2],[0,3,4]]

› Output: [false,true]

💡 Note: Query 1: path 0→3 with limit 2. Only edge (1,2) and (2,3) have weight < 2, but 0 is not connected. Query 2: path 0→3 with limit 4. Edges (0,1), (1,2), (2,3) all have weight < 4, so path 0→1→2→3 exists.

Example 2 — No Valid Path

$ Input: n = 3, edges = [[0,1,10],[1,2,5]], queries = [[0,2,3]]

› Output: [false]

💡 Note: Query: path 0→2 with limit 3. All edges have weight ≥ 3, so no valid path exists.

Example 3 — Direct Connection

$ Input: n = 2, edges = [[0,1,2]], queries = [[0,1,3],[0,1,1]]

› Output: [true,false]

💡 Note: Query 1: path 0→1 with limit 3. Edge weight 2 < 3, so direct path exists. Query 2: path 0→1 with limit 1. Edge weight 2 ≥ 1, so no valid path.

Constraints

2 ≤ n ≤ 10⁴
0 ≤ edges.length ≤ 10⁴
edges[i].length == 3
0 ≤ ui, vi < n
ui ≠ vi
0 ≤ disi ≤ 10⁹
0 ≤ queries.length ≤ 10⁴
queries[j].length == 3
0 ≤ pj, qj < n
pj ≠ qj
0 ≤ limitj ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Graph with weighted edges and connectivity queries

Filter Edges

Keep only edges with weight < query limit

Check Connectivity

Determine if path exists between query nodes

Key Takeaway

🎯 Key Insight: Sort edges and queries to process offline, avoiding repeated graph reconstruction

Asked in

G Google 25 f Facebook 18 a Amazon 15 M Microsoft 12

This problem requires checking connectivity between nodes using only edges with weight below a limit. The key insight is to use Union-Find with offline processing: sort edges by weight and queries by limit, then process them together to avoid rebuilding the graph for each query. Best approach is Union-Find with sorting. Time: O((E + Q) log (E + Q)), Space: O(N + Q)

Common Approaches

Approach	Time	Space	Notes
✓ Union-Find with Offline Processing	O((E + Q) log (E + Q) + E α(N))	O(N + Q)	Sort edges and queries, process offline using Union-Find
Brute Force DFS	O(Q × (E + N))	O(E + N)	For each query, run DFS using only edges with distance < limit

Union-Find with Offline Processing — Algorithm Steps

Sort edges by weight ascending
Sort queries by limit, keeping original indices
Process edges and queries together using Union-Find
For each query limit, add all valid edges then check connectivity

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Data

Sort edges by weight and queries by limit

Process Together

Add edges incrementally and answer queries

Union-Find

Track connectivity efficiently

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 10000
#define MAX_E 10000
#define MAX_Q 10000

typedef struct {
    int u, v, weight;
} Edge;

typedef struct {
    int p, q, limit, origIdx;
} Query;

int parent[MAX_N], rank_arr[MAX_N];

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    
    if (rank_arr[px] < rank_arr[py]) {
        int temp = px; px = py; py = temp;
    }
    parent[py] = px;
    if (rank_arr[px] == rank_arr[py]) {
        rank_arr[px]++;
    }
}

bool connected(int x, int y) {
    return find(x) == find(y);
}

int compareEdges(const void* a, const void* b) {
    return ((Edge*)a)->weight - ((Edge*)b)->weight;
}

int compareQueries(const void* a, const void* b) {
    return ((Query*)a)->limit - ((Query*)b)->limit;
}

void solution(int n, Edge* edges, int edgeCount, Query* queries, int queryCount, bool* results) {
    // Initialize Union-Find
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank_arr[i] = 0;
    }
    
    // Sort edges by weight
    qsort(edges, edgeCount, sizeof(Edge), compareEdges);
    
    // Sort queries by limit
    qsort(queries, queryCount, sizeof(Query), compareQueries);
    
    int edgeIdx = 0;
    for (int i = 0; i < queryCount; i++) {
        // Add all edges with weight < limit
        while (edgeIdx < edgeCount && edges[edgeIdx].weight < queries[i].limit) {
            unite(edges[edgeIdx].u, edges[edgeIdx].v);
            edgeIdx++;
        }
        
        // Check if p and q are connected
        results[queries[i].origIdx] = connected(queries[i].p, queries[i].q);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simple parsing for demo
    Edge edges[MAX_E];
    Query queries[MAX_Q];
    int edgeCount = 3, queryCount = 2;
    
    // Example data
    edges[0] = (Edge){0, 1, 3};
    edges[1] = (Edge){1, 2, 1};
    edges[2] = (Edge){2, 3, 1};
    
    queries[0] = (Query){0, 3, 2, 0};
    queries[1] = (Query){0, 3, 4, 1};
    
    bool results[MAX_Q];
    solution(n, edges, edgeCount, queries, queryCount, results);
    
    printf("[");
    for (int i = 0; i < queryCount; i++) {
        printf("%s", results[i] ? "true" : "false");
        if (i < queryCount - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((E + Q) log (E + Q) + E α(N))

Sort edges and queries, Union-Find operations with inverse Ackermann

⚡ Linearithmic

Space Complexity

O(N + Q)

Union-Find parent array and query results storage

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Union-Find with Offline Processing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler