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] is true, and false 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: [false,true] Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16. For the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query. For the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.
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: [true,false] Explanation: The above figure shows the given graph.
Constraints:
2 <= n <= 1051 <= edgeList.length, queries.length <= 105edgeList[i].length == 3queries[j].length == 30 <= ui, vi, pj, qj <= n - 1ui != vipj != qj1 <= disi, limitj <= 109This approach is based on using a Union-Find (Disjoint Set Union) data structure, which allows us to efficiently keep track of connected components in the graph. The strategy involves sorting both the edges and the queries based on the edge weights and the query limits, respectively. By processing these sorted lists, we can incrementally add edges to the Union-Find structure and query the connectivity status effectively.
This Python code implements the Union-Find with Path Compression technique. Initially, we sort the edgeList by distance and the queries by their limit. As we iterate over each query, we add edges to the Union-Find structure that are below the given query's limit. Then, we check if the specified nodes in the query belong to the same connected component.
C++
Java
JavaScript
C#
Time Complexity: O(E log E + Q log Q + (E + Q) α(n))
Space Complexity: O(n)
This approach involves modifying Kruskal's Minimum Spanning Tree algorithm to answer multiple queries about path existence. We leverage the intrinsic nature of Kruskal's algorithm which builds an MST (or a union-find structured graph) incrementally. For each query sorted by limit, we add edges with weight less than the limit to the union-find structure and check if two nodes are connected.
This Python code uses a slight modification of Kruskal's algorithm. We use the union-find data structure to progressively add edges before each query is processed, sorted by their limit. It essentially mimics building a Minimum Spanning Tree to answer each query about connectivity efficiently.
C++
Java
JavaScript
C#
Time Complexity: O(E log E + Q log Q + (E + Q) α(n))
Space Complexity: O(n)
| Approach | Complexity |
|---|---|
| Union-Find with Sorting | Time Complexity: O(E log E + Q log Q + (E + Q) α(n)) |
| Kruskal's Algorithm Modification | Time Complexity: O(E log E + Q log Q + (E + Q) α(n)) |
Unique Paths - Dynamic Programming - Leetcode 62 • NeetCode • 157,703 views views
Watch 9 more video solutions →Practice Checking Existence of Edge Length Limited Paths with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor