Checking Existence of Edge Length Limited Paths
HardPrompt
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 <= 109- There may be multiple edges between two nodes.
Approaches
2 approaches with complexity analysis and trade-offs.
The most straightforward approach is to process each query independently. For every query, we can construct a new graph that only includes edges with weights strictly less than the query's limit. After building this subgraph, we can use a standard graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS) to determine if a path exists between the two specified nodes.
Algorithm
- Create a boolean array
answerof sizequeries.length. - For each query
jfrom0toqueries.length - 1:- Let
p = queries[j][0],q = queries[j][1],limit = queries[j][2]. - Build an adjacency list
adjfor a graph withnnodes. - For each edge
(u, v, dist)inedgeList:- If
dist < limit, addvtoadj[u]andutoadj[v].
- If
- Use BFS or DFS to check if
qis reachable frompin the graph represented byadj. - If reachable, set
answer[j] = true, otherwiseanswer[j] = false.
- Let
- Return
answer.
Walkthrough
For each query (p, q, limit):
- Initialize an empty adjacency list to represent the graph for this specific query.
- Iterate through the entire
edgeList. If an edge's weight is less than the givenlimit, add it to the adjacency list. - Once the graph is constructed, perform a BFS starting from node
p. - Use a
visitedarray to keep track of nodes already visited to avoid cycles and redundant work. - A queue is used for the BFS. Initially, it contains only the start node
p. - In a loop, dequeue a node. If this node is the target node
q, we have found a path, and the result for this query istrue. - If the node is not the target, add all of its unvisited neighbors to the queue and mark them as visited.
- If the queue becomes empty and
qhas not been reached, it means there is no path betweenpandqunder the given limit. The result isfalse. - This process is repeated for all queries.
import java.util.*; class Solution { public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) { int qLen = queries.length; boolean[] answer = new boolean[qLen]; for (int i = 0; i < qLen; i++) { int p = queries[i][0]; int q = queries[i][1]; int limit = queries[i][2]; // Build graph for the current query List<List<Integer>> adj = new ArrayList<>(); for (int j = 0; j < n; j++) { adj.add(new ArrayList<>()); } for (int[] edge : edgeList) { if (edge[2] < limit) { adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } } // Check connectivity using BFS answer[i] = bfs(p, q, n, adj); } return answer; } private boolean bfs(int start, int end, int n, List<List<Integer>> adj) { if (start == end) return true; Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[n]; queue.offer(start); visited[start] = true; while (!queue.isEmpty()) { int curr = queue.poll(); if (curr == end) { return true; } for (int neighbor : adj.get(curr)) { if (!visited[neighbor]) { visited[neighbor] = true; queue.offer(neighbor); } } } return false; }}Complexity
Time
O(Q * (N + E)), where Q is the number of queries, N is the number of nodes, and E is the number of edges. For each of the Q queries, we iterate through all E edges to build the graph (O(E)) and then perform a traversal (O(N+E)).
Space
O(N + E) per query. In each iteration, we build an adjacency list which can take up to O(E) space, and the BFS requires O(N) space for the `visited` array and the queue.
Trade-offs
Pros
Simple to conceptualize and implement.
Cons
Highly inefficient due to redundant computations.
Will result in a 'Time Limit Exceeded' error for large inputs.
Solutions
Solution
class Solution {private int[] p;public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) { p = new int[n]; for (int i = 0; i < n; ++i) { p[i] = i; } Arrays.sort(edgeList, (a, b)->a[2] - b[2]); int m = queries.length; boolean[] ans = new boolean[m]; Integer[] qid = new Integer[m]; for (int i = 0; i < m; ++i) { qid[i] = i; } Arrays.sort(qid, (i, j)->queries[i][2] - queries[j][2]); int j = 0; for (int i : qid) { int a = queries[i][0], b = queries[i][1], limit = queries[i][2]; while (j < edgeList.length && edgeList[j][2] < limit) { int u = edgeList[j][0], v = edgeList[j][1]; p[find(u)] = find(v); ++j; } ans[i] = find(a) == find(b); } return ans; }private int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.