Checking Existence of Edge Length Limited Paths

Checking Existence of Edge Length Limited Paths - 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.

Given an array queries, where queries[j] = [pj, qj, limitj], your task is to determine for each queries[j] whether there is a path between pj and qj such that each edge on the path has a distance strictly less than limitj.

Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j], and false otherwise.

Input & Output

Example 1 — Basic Connectivity

$ Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,10],[0,2,5]]

› Output: [true,false]

💡 Note: For query [0,1,10]: Can use edge [0,1,2] since 2 < 10. For query [0,2,5]: Edge [1,2,4] works (4 < 5) but need path 0→1→2, so also need [0,1,2] (2 < 5) ✓. Actually there's direct edge [2,0,8] but 8 > 5. Path 0→1→2 uses edges with weights 2,4 both < 5, so answer is true.

Example 2 — No Valid Path

$ Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,20],[3,4,15]], queries = [[0,4,14]]

› Output: [false]

💡 Note: To go from 0 to 4, must use path 0→1→2→3→4. Edge weights are [10,5,20,15]. Since edge [2,3,20] has weight 20 ≥ 14, no valid path exists.

Example 3 — Multiple Valid Paths

$ Input: n = 4, edgeList = [[0,1,3],[1,3,1],[0,2,7],[2,3,2]], queries = [[0,3,8]]

› Output: [true]

💡 Note: Two paths exist: 0→1→3 (weights 3,1 both < 8) and 0→2→3 (weights 7,2 both < 8). Both paths are valid, so answer is true.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ edgeList.length, queries.length ≤ 10⁵
edgeList[i].length == 3
queries[j].length == 3
0 ≤ u_i, v_i, p_j, q_j ≤ n - 1
u_i ≠ v_i
p_j ≠ q_j
1 ≤ dis_i, limit_j ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Graph with weighted edges and connectivity queries

Filter Edges

For each query, consider only edges under weight limit

Check Path

Determine if valid path exists between query nodes

Key Takeaway

🎯 Key Insight: Sort edges and queries to process them offline, building connectivity incrementally with Union-Find for optimal performance

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to process queries offline by sorting both edges and queries, then using Union-Find to incrementally build connectivity. The brute force DFS approach has O(Q×(V+E)) time complexity, while the optimal Union-Find solution achieves O((E+Q) log (E+Q) + (E+Q)α(V)) time complexity. Best approach is Union-Find with sorting: Time: O((E+Q) log (E+Q)), Space: O(V+Q).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(Q × (V + E))	O(V)	For each query, run DFS to find valid path using only edges under limit
Union-Find with Sorting	O(E log E + Q log Q + (E + Q) α(V))	O(V + Q)	Sort edges and queries, process offline using Union-Find to track connectivity

Brute Force DFS — Algorithm Steps

Step 1: For each query, start DFS from source node
Step 2: Only traverse edges with weight < limit
Step 3: Return true if destination is reachable, false otherwise

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Processing

For each query [p,q,limit], start DFS from node p

Edge Filtering

Only traverse edges with weight < limit

Path Search

Continue DFS until target q is found or no more paths

Code -

solution.c — C

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

#define MAX_NODES 1000
#define MAX_EDGES 10000

struct Edge {
    int neighbor;
    int weight;
    struct Edge* next;
};

struct Edge* graph[MAX_NODES];
bool visited[MAX_NODES];

bool dfs(int node, int target, int limit) {
    if (node == target) return true;
    visited[node] = true;
    
    struct Edge* curr = graph[node];
    while (curr) {
        if (!visited[curr->neighbor] && curr->weight < limit) {
            if (dfs(curr->neighbor, target, limit)) {
                return true;
            }
        }
        curr = curr->next;
    }
    return false;
}

void addEdge(int u, int v, int w) {
    struct Edge* edge1 = malloc(sizeof(struct Edge));
    edge1->neighbor = v;
    edge1->weight = w;
    edge1->next = graph[u];
    graph[u] = edge1;
    
    struct Edge* edge2 = malloc(sizeof(struct Edge));
    edge2->neighbor = u;
    edge2->weight = w;
    edge2->next = graph[v];
    graph[v] = edge2;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Initialize graph
    for (int i = 0; i < MAX_NODES; i++) {
        graph[i] = NULL;
    }
    
    // Parse edgeList and queries (simplified)
    // In real implementation, would parse JSON format
    
    printf("[true,false]\n"); // Placeholder output
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(Q × (V + E))

Q queries × DFS traversal of V vertices and E edges

✓ Linear Growth

Space Complexity

O(V)

DFS recursion stack depth up to V vertices

✓ Linear Space

23.0K Views

Medium Frequency

~35 min Avg. Time

890 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

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler