# Checking Existence of Edge Length Limited Paths
**Difficulty:** HARD
[External](https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths)
Canonical: https://scaleengineer.com/dsa/problems/checking-existence-of-edge-length-limited-paths
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Array, Graph
---
## Problem
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:**

![](https://assets.glich.co/dsa/checking-existence-of-edge-length-limited-paths/image0.png) 

**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:**

![](https://assets.glich.co/dsa/checking-existence-of-edge-length-limited-paths/image1.png) 

**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 <= 105`
* `1 <= edgeList.length, queries.length <= 105`
* `edgeList[i].length == 3`
* `queries[j].length == 3`
* `0 <= ui, vi, pj, qj <= n - 1`
* `ui != vi`
* `pj != qj`
* `1 <= disi, limitj <= 109`
* There may be **multiple** edges between two nodes.

# Approaches
## Brute-Force with Graph Traversal per Query
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.
**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.
**Pros:** Simple to conceptualize and implement.
**Cons:** Highly inefficient due to redundant computations.; Will result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
For each query `(p, q, limit)`:
1.  Initialize an empty adjacency list to represent the graph for this specific query.
2.  Iterate through the entire `edgeList`. If an edge's weight is less than the given `limit`, add it to the adjacency list.
3.  Once the graph is constructed, perform a BFS starting from node `p`.
4.  Use a `visited` array to keep track of nodes already visited to avoid cycles and redundant work.
5.  A queue is used for the BFS. Initially, it contains only the start node `p`.
6.  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 is `true`.
7.  If the node is not the target, add all of its unvisited neighbors to the queue and mark them as visited.
8.  If the queue becomes empty and `q` has not been reached, it means there is no path between `p` and `q` under the given limit. The result is `false`.
9.  This process is repeated for all queries.

```java
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;
    }
}
```
### Algorithm
- Create a boolean array `answer` of size `queries.length`.
- For each query `j` from `0` to `queries.length - 1`:
    - Let `p = queries[j][0]`, `q = queries[j][1]`, `limit = queries[j][2]`.
    - Build an adjacency list `adj` for a graph with `n` nodes.
    - For each edge `(u, v, dist)` in `edgeList`:
        - If `dist < limit`, add `v` to `adj[u]` and `u` to `adj[v]`.
    - Use BFS or DFS to check if `q` is reachable from `p` in the graph represented by `adj`.
    - If reachable, set `answer[j] = true`, otherwise `answer[j] = false`.
- Return `answer`.

## Offline Processing with Union-Find
A much more efficient solution involves processing the queries "offline". The key observation is that if a path exists for a certain `limit`, it also exists for any larger limit. This monotonic property allows us to sort both the edges (by weight) and the queries (by limit). We can then iterate through the sorted queries, and for each query, add all edges with weights less than its limit to a single, evolving graph structure. The Union-Find (or Disjoint Set Union) data structure is perfect for efficiently tracking the connected components of this graph as we add edges.
**Time:** O(E log E + Q log Q + (E + Q) * α(N)). Sorting the edges takes O(E log E), and sorting the queries takes O(Q log Q). The main loop involves iterating through all queries and edges once. The total time for all Union-Find operations (E unions and Q finds) is nearly linear, O((E + Q) * α(N)), where α(N) is the very slow-growing inverse Ackermann function. The complexity is dominated by the sorting steps. · **Space:** O(N + Q). We need O(N) space for the Union-Find data structure's parent and rank arrays. We also need O(Q) space to store the augmented queries with their original indices and for the final answer array.
**Pros:** Highly efficient and optimal for the given constraints.; Avoids redundant work by processing edges and queries in a sorted order.; The Union-Find data structure provides near-constant time complexity for connectivity checks.
**Cons:** More complex to implement compared to the brute-force approach.; Requires knowledge of the Union-Find data structure and offline processing techniques.
### Explanation
The algorithm works as follows:
1.  **Sort Edges and Queries**: Sort the `edgeList` by weight and the `queries` by their `limit`, both in ascending order. Since we need to return the answers in the original order of queries, we first augment the `queries` array to keep track of each query's original index.
2.  **Initialize Union-Find**: Create a Union-Find data structure to manage the connectivity of the `n` nodes. Initially, each node is in its own component.
3.  **Process Queries Incrementally**: Iterate through the sorted queries. Maintain a pointer to the current edge in the sorted `edgeList`.
4.  For each query, advance the edge pointer, adding all edges whose weights are less than the current query's `limit` to the Union-Find structure. Adding an edge `(u, v)` means performing a `union(u, v)` operation, which merges the components containing `u` and `v`.
5.  **Check Connectivity**: After adding all valid edges for the current query's limit, check if the query's nodes `p` and `q` are connected. This is a simple check: `find(p) == find(q)`. If they have the same root in the Union-Find structure, they are in the same connected component, and a path exists.
6.  **Store Result**: Store the boolean result in an answer array at the query's original index.
7.  By the end, we will have processed all queries efficiently because each edge is considered and added to the Union-Find structure at most once.

```java
import java.util.Arrays;

class Solution {
    class UnionFind {
        private int[] parent;
        private int[] rank;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int i) {
            if (parent[i] == i) {
                return i;
            }
            return parent[i] = find(parent[i]); // Path compression
        }

        public void union(int i, int j) {
            int rootI = find(i);
            int rootJ = find(j);
            if (rootI != rootJ) {
                // Union by rank
                if (rank[rootI] > rank[rootJ]) {
                    parent[rootJ] = rootI;
                } else if (rank[rootI] < rank[rootJ]) {
                    parent[rootI] = rootJ;
                } else {
                    parent[rootJ] = rootI;
                    rank[rootI]++;
                }
            }
        }
    }

    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        // Sort edges by weight
        Arrays.sort(edgeList, (a, b) -> a[2] - b[2]);

        // Add original index to queries and sort by limit
        int qLen = queries.length;
        int[][] queriesWithIndex = new int[qLen][4];
        for (int i = 0; i < qLen; i++) {
            queriesWithIndex[i][0] = queries[i][0];
            queriesWithIndex[i][1] = queries[i][1];
            queriesWithIndex[i][2] = queries[i][2];
            queriesWithIndex[i][3] = i;
        }
        Arrays.sort(queriesWithIndex, (a, b) -> a[2] - b[2]);

        UnionFind uf = new UnionFind(n);
        boolean[] answer = new boolean[qLen];
        int edgeIndex = 0;

        for (int i = 0; i < qLen; i++) {
            int p = queriesWithIndex[i][0];
            int q = queriesWithIndex[i][1];
            int limit = queriesWithIndex[i][2];
            int originalIndex = queriesWithIndex[i][3];

            // Add all edges with weight less than the current query's limit
            while (edgeIndex < edgeList.length && edgeList[edgeIndex][2] < limit) {
                uf.union(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
                edgeIndex++;
            }

            // Check if p and q are connected
            if (uf.find(p) == uf.find(q)) {
                answer[originalIndex] = true;
            } else {
                answer[originalIndex] = false;
            }
        }

        return answer;
    }
}
```
### Algorithm
- Create a `UnionFind` class with `find` and `union` operations, optimized with path compression and union by rank/size.
- Augment the `queries` array to store their original indices: `queriesWithIndex[i] = {queries[i][0], queries[i][1], queries[i][2], i}`.
- Sort `edgeList` by weight in ascending order.
- Sort `queriesWithIndex` by limit in ascending order.
- Initialize a `UnionFind` structure for `n` nodes.
- Initialize a boolean array `answer` of size `queries.length`.
- Initialize an edge pointer `edgeIdx = 0`.
- For each sorted query `(p, q, limit, originalIdx)`:
    - While `edgeIdx < edgeList.length` and `edgeList[edgeIdx][2] < limit`:
        - `union(edgeList[edgeIdx][0], edgeList[edgeIdx][1])`.
        - `edgeIdx++`.
    - Check if `p` and `q` are in the same component: `find(p) == find(q)`.
    - Store the result in `answer[originalIdx]`.
- Return `answer`.

# Solutions
### Java

```java
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];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>> &edgeList,
                                         vector<vector<int>> &queries) {
    vector<int> p(n);
    iota(p.begin(), p.end(), 0);
    sort(edgeList.begin(), edgeList.end(),
         [](auto &a, auto &b) { return a[2] < b[2]; });
    function<int(int)> find = [&](int x) -> int {
      if (p[x] != x)
        p[x] = find(p[x]);
      return p[x];
    };
    int m = queries.size();
    vector<bool> ans(m);
    vector<int> qid(m);
    iota(qid.begin(), qid.end(), 0);
    sort(qid.begin(), qid.end(),
         [&](int i, int j) { return 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.size() && 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;
  }
};

```

### Python

```python
class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]: def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] p = list(range(n)) edgeList . sort(key=lambda x: x[2]) j = 0 ans = [False] * len(queries) for i, (a, b, limit) in sorted(enumerate(queries), key=lambda x: x[1][2]): while j < len(edgeList) and edgeList[j][2] < limit: u, v, _ = edgeList[j] p[find(u)] = find(v) j += 1 ans[i] = find(a) == find(b) return ans

```