# Path Existence Queries in a Graph II
**Difficulty:** HARD
[External](https://leetcode.com/problems/path-existence-queries-in-a-graph-ii)
Canonical: https://scaleengineer.com/dsa/problems/path-existence-queries-in-a-graph-ii
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Graph
---
## Problem
You are given an integer `n` representing the number of nodes in a graph, labeled from 0 to `n - 1`.

You are also given an integer array `nums` of length `n` and an integer `maxDiff`.

An **undirected** edge exists between nodes `i` and `j` if the **absolute** difference between `nums[i]` and `nums[j]` is **at most** `maxDiff` (i.e., `|nums[i] - nums[j]| <= maxDiff`).

You are also given a 2D integer array `queries`. For each `queries[i] = [ui, vi]`, find the **minimum** distance between nodes `ui` and `vi`. If no path exists between the two nodes, return -1 for that query.

Return an array `answer`, where `answer[i]` is the result of the `ith` query.

**Note:** The edges between the nodes are unweighted.

**Example 1:**

**Input:** n = 5, nums = \[1,8,3,4,2\], maxDiff = 3, queries = \[\[0,3\],\[2,4\]\]

**Output:** \[1,1\]

**Explanation:**

The resulting graph is:

![](https://assets.glich.co/dsa/path-existence-queries-in-a-graph-ii/image0.png)

| Query    | Shortest Path | Minimum Distance |
| -------- | ------------- | ---------------- |
| \[0, 3\] | 0 → 3         | 1                |
| \[2, 4\] | 2 → 4         | 1                |

Thus, the output is `[1, 1]`.

**Example 2:**

**Input:** n = 5, nums = \[5,3,1,9,10\], maxDiff = 2, queries = \[\[0,1\],\[0,2\],\[2,3\],\[4,3\]\]

**Output:** \[1,2,-1,1\]

**Explanation:**

The resulting graph is:

![](https://assets.glich.co/dsa/path-existence-queries-in-a-graph-ii/image1.png)

| Query    | Shortest Path | Minimum Distance |
| -------- | ------------- | ---------------- |
| \[0, 1\] | 0 → 1         | 1                |
| \[0, 2\] | 0 → 1 → 2     | 2                |
| \[2, 3\] | None          | \-1              |
| \[4, 3\] | 3 → 4         | 1                |

Thus, the output is `[1, 2, -1, 1]`.

**Example 3:**

**Input:** n = 3, nums = \[3,6,1\], maxDiff = 1, queries = \[\[0,0\],\[0,1\],\[1,2\]\]

**Output:** \[0,-1,-1\]

**Explanation:**

There are no edges between any two nodes because:

* Nodes 0 and 1: `|nums[0] - nums[1]| = |3 - 6| = 3 > 1`
* Nodes 0 and 2: `|nums[0] - nums[2]| = |3 - 1| = 2 > 1`
* Nodes 1 and 2: `|nums[1] - nums[2]| = |6 - 1| = 5 > 1`

Thus, no node can reach any other node, and the output is `[0, -1, -1]`.

**Constraints:**

* `1 <= n == nums.length <= 105`
* `0 <= nums[i] <= 105`
* `0 <= maxDiff <= 105`
* `1 <= queries.length <= 105`
* `queries[i] == [ui, vi]`
* `0 <= ui, vi < n`

# Approaches
## Brute-Force BFS for Each Query
The most straightforward approach is to treat the problem as a series of shortest path queries on an implicitly defined graph. For each query `[u, v]`, we can run a Breadth-First Search (BFS) starting from node `u` to find the shortest distance to node `v`. BFS is suitable here because all edges are unweighted, meaning each edge contributes 1 to the path length.
**Time:** O(Q * N^2), where Q is the number of queries and N is the number of nodes. For each of the Q queries, we perform a BFS. A single BFS can take up to O(N^2) time because for each of the N nodes, we might iterate through all N other nodes to find its neighbors. · **Space:** O(N) for each BFS run to store the queue, distance array, and visited set. Since we run queries sequentially, the space can be reused.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient due to its high time complexity.; The neighbor finding step, which iterates through all `n` nodes, is a major bottleneck.; Will likely result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The algorithm for each query `[u, v]` is as follows:

1.  Initialize a queue for the BFS and add the starting node `u` with a distance of 0.
2.  Use a `visited` array or set to keep track of nodes that have already been added to the queue, to avoid cycles and redundant computations. Mark `u` as visited.
3.  Use a `distance` array to store the shortest distance from `u` to every other node, initialized to infinity except for `distance[u] = 0`.
4.  While the queue is not empty, dequeue a node `curr`.
5.  If `curr` is the target node `v`, we have found the shortest path. The distance is `distance[curr]`. We can terminate the BFS for this query and return the result.
6.  If `curr` is not the target, we need to find all its neighbors. We iterate through all other nodes `j` from `0` to `n-1`.
7.  For each node `j`, if it has not been visited and an edge exists between `curr` and `j` (i.e., `|nums[curr] - nums[j]| <= maxDiff`), we mark `j` as visited, update its distance (`distance[j] = distance[curr] + 1`), and enqueue it.
8.  If the queue becomes empty and we have not reached `v`, it means there is no path between `u` and `v`. In this case, the distance is -1.

This entire process is repeated for every query in the `queries` array.

```java
class Solution {
    public int[] minDistance(int n, int[] nums, int maxDiff, int[][] queries) {
        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            answer[i] = bfs(queries[i][0], queries[i][1], n, nums, maxDiff);
        }
        return answer;
    }

    private int bfs(int start, int end, int n, int[] nums, int maxDiff) {
        if (start == end) {
            return 0;
        }

        Queue<Integer> queue = new LinkedList<>();
        int[] dist = new int[n];
        Arrays.fill(dist, -1);

        queue.offer(start);
        dist[start] = 0;

        while (!queue.isEmpty()) {
            int u = queue.poll();

            if (u == end) {
                return dist[u];
            }

            // Find neighbors by iterating through all nodes
            for (int v = 0; v < n; v++) {
                if (dist[v] == -1 && Math.abs(nums[u] - nums[v]) <= maxDiff) {
                    dist[v] = dist[u] + 1;
                    queue.offer(v);
                }
            }
        }

        return -1;
    }
}
```
### Algorithm
- For each query `(u, v)` in `queries`:
  - Initialize a queue and add `(u, 0)` (node, distance).
  - Initialize a `distance` array of size `n` with -1.
  - Set `distance[u] = 0`.
  - While the queue is not empty:
    - Dequeue the current node `curr`.
    - If `curr` is `v`, the shortest distance is found. Store it and break the loop.
    - Iterate through all nodes `j` from `0` to `n-1`:
      - If `j` is unvisited (`distance[j] == -1`) and `|nums[curr] - nums[j]| <= maxDiff`:
        - Set `distance[j] = distance[curr] + 1`.
        - Enqueue `j`.
  - If `v` was not reached, the distance is -1.
- Return the array of computed distances.

## Optimized BFS with a Data Structure
The brute-force approach is slow because finding the neighbors of a node takes O(N) time. We can optimize this step using a data structure. For a given node `u`, its neighbors are all nodes `v` such that `nums[v]` falls within the range `[nums[u] - maxDiff, nums[u] + maxDiff]`. This is a range query problem.

We can maintain the set of *unvisited* nodes in a data structure that supports efficient range queries and deletions, such as a balanced binary search tree (BBST) or a segment tree. In Java, a `TreeSet` can serve as a BBST.
**Time:** O(Q * N log N) or O(Q * N log V_max) depending on the data structure, where V_max is the maximum value in `nums`. Each BFS takes O(N log N) because each of the N nodes is processed once, and each processing step involves operations (query, deletion) on the data structure that take logarithmic time. This is repeated for Q queries. · **Space:** O(N) to store the data structure (e.g., BBST) holding all nodes, plus the queue and distance/visited arrays for BFS.
**Pros:** Significantly faster than the brute-force approach.; Reduces the complexity of finding neighbors from O(N) to O(log N + K), where K is the number of neighbors.
**Cons:** More complex to implement correctly.; The time complexity is still too high for the given constraints where both N and Q can be large.; Requires re-initializing the data structure for each query, which is costly.
### Explanation
The improved algorithm for each query `(u, v)` is as follows:

1.  To handle nodes with the same `nums` value, we create pairs of `(value, index)` for each node.
2.  For each query, we populate a BBST (e.g., `TreeSet`) with pairs `(nums[i], i)` for all nodes `i` that are yet to be visited. The `TreeSet` will keep the nodes sorted by their `nums` value, and then by index as a tie-breaker.
3.  Start a BFS from node `u`. Initialize a queue and a `distance` array.
4.  Remove `(nums[u], u)` from the `TreeSet` and add `u` to the queue.
5.  While the queue is not empty, dequeue a node `curr`.
6.  To find its neighbors, perform a range query on the `TreeSet` for the value range `[nums[curr] - maxDiff, nums[curr] + maxDiff]`.
7.  The `TreeSet` efficiently provides all nodes within this value range. For each neighbor found:
    a.  Remove it from the `TreeSet` to mark it as visited.
    b.  Update its distance and add it to the queue.
8.  This process continues until the destination `v` is found or the queue is empty.

Each node is added to the queue once and removed from the `TreeSet` once. The cost of finding neighbors for a node is dominated by the range query on the `TreeSet`, which is `O(log N + K)`, where `K` is the number of neighbors found. Summed over the entire BFS, this leads to a much better time complexity per query.

```java
class Solution {
    public int[] minDistance(int n, int[] nums, int maxDiff, int[][] queries) {
        // Pre-sort nodes by value to potentially group nodes with same value
        List<List<Integer>> valToNodes = new ArrayList<>();
        for (int i = 0; i < 100001; i++) {
            valToNodes.add(new ArrayList<>());
        }
        for (int i = 0; i < n; i++) {
            valToNodes.get(nums[i]).add(i);
        }

        int[] answer = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            answer[i] = bfsWithDS(queries[i][0], queries[i][1], n, nums, maxDiff, valToNodes);
        }
        return answer;
    }

    private int bfsWithDS(int start, int end, int n, int[] nums, int maxDiff, List<List<Integer>> valToNodes) {
        if (start == end) {
            return 0;
        }

        Queue<Integer> queue = new LinkedList<>();
        int[] dist = new int[n];
        Arrays.fill(dist, -1);

        // Use a data structure for unvisited nodes. A TreeSet of values works.
        TreeSet<Integer> unvisitedValues = new TreeSet<>();
        for (int val : nums) {
            unvisitedValues.add(val);
        }
        // We need a way to mark nodes as visited, not just values.
        boolean[] visited = new boolean[n];

        queue.offer(start);
        dist[start] = 0;
        visited[start] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();

            if (u == end) {
                return dist[u];
            }

            int low = Math.max(0, nums[u] - maxDiff);
            int high = Math.min(100000, nums[u] + maxDiff);

            // Query the TreeSet for the range of values
            Integer nextVal = unvisitedValues.ceiling(low);
            while (nextVal != null && nextVal <= high) {
                for (int v : valToNodes.get(nextVal)) {
                    if (!visited[v]) {
                        visited[v] = true;
                        dist[v] = dist[u] + 1;
                        queue.offer(v);
                    }
                }
                // Once all nodes for a value are visited, remove the value from the set
                unvisitedValues.remove(nextVal);
                nextVal = unvisitedValues.ceiling(low);
            }
        }

        return -1;
    }
}
```
*Note: The provided Java code snippet illustrates the concept. A fully optimized implementation might require careful handling of removing nodes from the `valToNodes` lists or using a more complex structure to avoid re-visiting nodes with the same value.*
### Algorithm
- For each query `(u, v)`:
  - Initialize a data structure (e.g., a BBST or a list of `TreeSet`s for each value) containing all unvisited nodes, structured for efficient range queries on `nums` values.
  - Initialize a queue, a `distance` array, and a `visited` array.
  - Add `u` to the queue, set its distance to 0, mark it as visited, and remove it from the unvisited data structure.
  - While the queue is not empty:
    - Dequeue `curr`.
    - If `curr` is `v`, return its distance.
    - Perform a range query on the unvisited data structure for `[nums[curr] - maxDiff, nums[curr] + maxDiff]`.
    - For each node `j` found in the range:
      - Remove `j` from the unvisited data structure.
      - Set `distance[j] = distance[curr] + 1` and enqueue `j`.
  - If `v` was not reached, return -1.