1697. Checking Existence of Edge Length Limited Paths

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

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

Return a boolean array answer, where answer.length == queries.length and the $j^{th}$ 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 $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 \leq n \leq 10^5$
• $1 \leq$ edgeList.length, queries.length $\leq 10^5$
• edgeList[i].length == 3
• queries[j].length == 3
• $0 \leq u_i, v_i, p_j, q_j \leq n - 1$
• $u_i \neq v_i$
• $p_j \neq q_j$
• $1 \leq \text{dis}_ i, \text{limit}_ j \leq 10^9$
• There may be multiple edges between two nodes.

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 $\text{limit}_ j$. We can then check if $p_j$ and $q_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 $p_j$ to $q_j$.

Let $M$ denote the size of edgeList and let $Q$ denote the size of queries.

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

The BFS solution answers queries in $\mathcal{O}(N+M)$ in the worst case which leads to a total time complexity of $\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 $\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 $\text{limit}_ j$. Our queries are sorted by the value of $\text{limit}_ j$ so $\text{limit}_ {j+1}$ will always be greater or equal to $\text{limit}_ j$. Since $\text{limit}_ {j+1} \geq \text{limit}_ j$, we can observe that all edges in the DSU for query $j$ will always be part of the DSU for query $j+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 $4$, it will be added in the DSU for queries with limits of $5,7,$ and $9$ as $4\leq 5,7,9$. We can see that once we reach the query with the limit of $5$, we will include the edge with distance $4$ 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 $\mathcal{O}(M\log{N})$ to our time complexity. Answering all $Q$ queries will contribute $\mathcal{O}(Q\log{N})$. Thus, our final time complexity will be $\mathcal{O}((Q+M)\log{N})$.

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

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

Space Complexity

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

Space Complexity: $\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