1697. Checking Existence of Edge Length Limited Paths

An undirected graph of nn nodes is defined by edgeList, where edgeList[i] = [uiu_i, viv_i, disi\text{dis}_ i] denotes an edge between nodes uiu_i and viv_i with distance disi\text{dis}_ i. Note that there may be multiple edges between two nodes.

Given an array queries, where queries[j] = [pjp_j, qjq_j, limitj\text{limit} _ 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 limitj\text{limit}_ j.

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

Example 1:
Example

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 00 and 11 with distances 22 and 1616.
For the first query, between 00 and 11 there is no path where each distance is less than 22, thus we return false for this query.
For the second query, there is a path (00 -> 11 -> 22) of two edges with distances less than 55, thus we return true for this query.

Example 2: 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:

  • 2n1052 \leq n \leq 10^5
  • 11 \leq edgeList.length, queries.length 105\leq 10^5
  • edgeList[i].length == 3
  • queries[j].length == 3
  • 0ui,vi,pj,qjn10 \leq u_i, v_i, p_j, q_j \leq n - 1
  • uiviu_i \neq v_i
  • pjqjp_j \neq q_j
  • 1disi,limitj1091 \leq \text{dis}_ i, \text{limit}_ j \leq 10^9
  • There may be multiple edges between two nodes.

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 limitj\text{limit}_ j. We can then check if pjp_j and qjq_j 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 pjp_j to qjq_j.

Let MM denote the size of edgeList and let QQ denote the size of queries.

With the DSU solution, we'll answer each query in O(MlogN)\mathcal{O}(M\log{N}). This leads to a total time complexity of O(QMlogN)\mathcal{O}(QM\log{N}).

The BFS solution answers queries in O(N+M)\mathcal{O}(N+M) in the worst case which leads to a total time complexity of O(Q(N+M))\mathcal{O}(Q(N+M)).

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 limitj\text{limit}_ j. 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 limitj\text{limit}_ j. Our queries are sorted by the value of limitj\text{limit}_ j so limitj+1\text{limit}_ {j+1} will always be greater or equal to limitj\text{limit}_ j. Since limitj+1limitj\text{limit}_ {j+1} \geq \text{limit}_ j, we can observe that all edges in the DSU for query jj will always be part of the DSU for query j+1j+1. 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 44, it will be added in the DSU for queries with limits of 5,7,5,7, and 99 as 45,7,94\leq 5,7,9. We can see that once we reach the query with the limit of 55, we will include the edge with distance 44 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 O(MlogN)\mathcal{O}(M\log{N}) to our time complexity. Answering all QQ queries will contribute O(QlogN)\mathcal{O}(Q\log{N}). Thus, our final time complexity will be O((Q+M)logN)\mathcal{O}((Q+M)\log{N}).

Time Complexity: O((Q+M)logN)\mathcal{O}((Q+M)\log{N}).

Bonus: We can use union by rank mentioned here to improve the time complexity of DSU operations from O(logN)\mathcal{O}(\log{N}) to O(α(N))\mathcal{O}(\alpha(N)).

Space Complexity

Our DSU takes O(N)\mathcal{O}(N) space and storing the answers to all QQ queries takes O(Q)\mathcal{O}(Q) space so our final space complexity is O(N+Q)\mathcal{O}(N+Q).

Space Complexity: O(N+Q)\mathcal{O}(N+Q)

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
Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Depth first search is equivalent to which of the tree traversal order?

Solution Implementation

Not Sure What to Study? Take the 2-min Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?

Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫