Checking Existence of Edge Length Limited Paths
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], 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 j^th value of answer is true if there is such a path for queries[j], 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]For the first query there is no path from 0 to 1 with every edge distance less than 2, while for the second query the path 0 -> 1 -> 2 uses edges with distances less than 5.
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]There is a valid path from 0 to 4 using only edges with distances less than 14, but no valid path from 1 to 4 using only edges with distances less than 13.
Constraints
- 2 <= n <= 10^5
- 1 <= edgeList.length, queries.length <= 10^5
- edgeList[i].length == 3
- queries[j].length == 3
- 0 <= ui, vi, pj, qj <= n - 1
- ui != vi
- pj != qj
- 1 <= disi, limitj <= 10^9
- There may be multiple edges between two nodes.
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.