LeetCode 1697. Checking Existence of Edge Length Limited Paths Solution
An undirected graph of nodes is defined by edgeList
, where edgeList[i]
= [, , ] denotes an edge between nodes and with distance . Note that there may be multiple edges between two nodes.
Given an array queries
, where queries[j]
= [, , ], 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 .
Return a boolean array answer
, where answer.length == queries.length
and the value of answer
is true
if there is 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]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between and with distances and .
For the first query, between and there is no path where each distance is less than , thus we return false for this query.
For the second query, there is a path ( -> -> ) of two edges with distances less than , 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:
-
edgeList.length, queries.length
edgeList[i].length == 3
queries[j].length == 3
- There may be multiple edges between two nodes.
Problem Link: https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/
Solution
Brute Force
When we see problems about whether or not two nodes are connected, we should think about DSU as it answers queries related to connectivity very quickly. For each query queries[j]
, we'll initialize a DSU and merge nodes connected by edges with a distance strictly less than . We can then check if and have the same id/leader in the DSU to determine if they are connected. An alternative is to build the graph and run a BFS on it to check for connectivity from to .
Let denote the size of edgeList
and let denote the size of queries
.
With the DSU solution, we'll answer each query in . This leads to a total time complexity of .
The BFS solution answers queries in in the worst case which leads to a total time complexity of .
Full Solution
We will focus on the brute force DSU solution and extend it to obtain the full solution. The reason why this solution is inefficient is because we rebuild the DSU for every query. Let's find a way to answer all the queries without rebuilding the DSU each time.
We can accomplish this by answering the queries by non-decreasing . If we answer queries in this order, we'll only need to build the DSU once. Why is this the case? First, we'll take a step back to our brute force solution. Let's look at what edges each DSU contains for each . Our queries are sorted by the value of so will always be greater or equal to . Since , we can observe that all edges in the DSU for query will always be part of the DSU for query . We can also observe that this means once an edge is added into the DSU for some query, it will stay in the DSU for the remaining queries.
Example
For example, let's say we had queries with the following limits: [1,3,5,7,9]
If edgeList
had an edge with distance , it will be added in the DSU for queries with limits of and as . We can see that once we reach the query with the limit of , we will include the edge with distance into our DSU and it will stay there for the remaining queries.
Some details for implementation
For each query, we should include another variable which is the index of that query. This is important as we have to return the answers to the queries in the order they were asked.
Since we are adding edges in order from least distance to greatest distance, it would be convenient to sort the edges by the distance value and have some pointer to indicate which edges have been added so far.
Time Complexity
Each edge is added at most once so this contributes to our time complexity. Answering all queries will contribute . Thus, our final time complexity will be .
Time Complexity: .
Bonus: We can use union by rank mentioned here to improve the time complexity of DSU operations from to .
Space Complexity
Our DSU takes space and storing the answers to all queries takes space so our final space complexity is .
Space Complexity:
C++ Solution
1class Solution {
2 vector<int> parent;
3 int find(int x) { // finds the id/leader of a node
4 if (parent[x] == x) {
5 return x;
6 }
7 parent[x] = find(parent[x]);
8 return parent[x];
9 }
10 void Union(int x, int y) { // merges two disjoint sets into one set
11 x = find(x);
12 y = find(y);
13 parent[x] = y;
14 }
15 static bool comp(vector<int>& a, vector<int>& b) { // sorting comparator
16 return a[2] < b[2];
17 }
18
19 public:
20 vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList,
21 vector<vector<int>>& queries) {
22 parent.resize(n);
23 for (int i = 0; i < n; i++) {
24 parent[i] = i;
25 }
26 sort(edgeList.begin(), edgeList.end(), comp); // sort edges by value for distance
27 for (int j = 0; j < queries.size();
28 j++) { // keeps track of original index for each query
29 queries[j].push_back(j);
30 }
31 sort(queries.begin(), queries.end(), comp); // sort queries by value for limit
32 int i = 0;
33 vector<bool> ans(queries.size());
34 for (vector<int> query : queries) {
35 int limit = query[2];
36 while (i < edgeList.size() &&
37 edgeList[i][2] < limit) { // keeps adding edges with distance < limit
38 int u = edgeList[i][0];
39 int v = edgeList[i][1];
40 Union(u, v);
41 i++;
42 }
43 int p = query[0];
44 int q = query[1];
45 int queryIndex = query[3];
46 if (find(p) == find(q)) { // checks if p and q are connected
47 ans[queryIndex] = true;
48 }
49 }
50 return ans;
51 }
52};
Java Solution
1class Solution {
2 private
3 int find(int x, int[] parent) { // finds the id/leader of a node
4 if (parent[x] == x) {
5 return x;
6 }
7 parent[x] = find(parent[x], parent);
8 return parent[x];
9 }
10 private
11 void Union(int x, int y, int[] parent) { // merges two disjoint sets into one set
12 x = find(x, parent);
13 y = find(y, parent);
14 parent[x] = y;
15 }
16 public
17 boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
18 int[] parent = new int[n];
19 for (int i = 0; i < n; i++) {
20 parent[i] = i;
21 }
22 Arrays.sort(edgeList, (a, b)->a[2] - b[2]); // sort edges by value for distance
23 for (int j = 0; j < queries.length;
24 j++) { // keeps track of original index for each query
25 queries[j] = new int[]{queries[j][0], queries[j][1], queries[j][2], j};
26 }
27 Arrays.sort(queries, (a, b)->a[2] - b[2]); // sort queries by value for limit
28 int i = 0;
29 boolean[] ans = new boolean[queries.length];
30 for (int j = 0; j < queries.length; j++) {
31 int[] query = queries[j];
32 int limit = query[2];
33 while (i < edgeList.length &&
34 edgeList[i][2] < limit) { // keeps adding edges with distance < limit
35 int u = edgeList[i][0];
36 int v = edgeList[i][1];
37 Union(u, v, parent);
38 i++;
39 }
40 int p = query[0];
41 int q = query[1];
42 int queryIndex = query[3];
43 if (find(p, parent) == find(q, parent)) { // checks if p and q are connected
44 ans[queryIndex] = true;
45 }
46 }
47 return ans;
48 }
49}
Python Solution
1class Solution: 2 def distanceLimitedPathsExist( 3 self, n: int, edgeList: List[List[int]], queries: List[List[int]] 4 ) -> List[bool]: 5 parent = [i for i in range(n)] 6 7 def find(x): # finds the id/leader of a node 8 if parent[x] == x: 9 return x 10 parent[x] = find(parent[x]) 11 return parent[x] 12 13 def Union(x, y): # merges two disjoint sets into one set 14 x = find(x) 15 y = find(y) 16 parent[x] = y 17 18 edgeList.sort(key=lambda x: x[2]) # sort edges by value for distance 19 for i in range(len(queries)): # keeps track of original index for each query 20 queries[i].append(i) 21 queries.sort(key=lambda x: x[2]) # sort queries by value for limit 22 i = 0 23 ans = [False for j in range(len(queries))] 24 for query in queries: 25 limit = query[2] 26 while ( 27 i < len(edgeList) and edgeList[i][2] < limit 28 ): # keeps adding edges with distance < limit 29 u = edgeList[i][0] 30 v = edgeList[i][1] 31 Union(u, v) 32 i += 1 33 p = query[0] 34 q = query[1] 35 queryIndex = query[3] 36 if find(p) == find(q): # checks if p and q are connected 37 ans[queryIndex] = True 38 return ans