Shortest Paths in a Value-Difference Graph
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
# Shortest Paths in a Value-Difference Graph
There are `n` nodes labeled `0` through `n - 1`. Node `i` has integer value `nums[i]`; these values are not necessarily sorted.
Nodes `i` and `j` have an undirected, unweighted edge exactly when `abs(nums[i] - nums[j]) <= maxDiff`.
For each pair `[u, v]` in `queries`, return the minimum number of edges in a path from `u` to `v`, or `-1` if no path exists. Return zero when `u == v`. The answers must appear in query order.
### C++ Interface
```cpp
class Solution {
public:
vector<int> pathExistenceQueries(int n, vector<int>& nums, int maxDiff,
vector<vector<int>>& queries);
};
```
### Examples
**Example 1**
```text
n = 6
nums = [7,1,4,10,4,20]
maxDiff = 3
queries = [[1,3],[4,0],[2,4],[0,5],[3,3]]
Output: [3,1,1,-1,0]
```
For `[1,3]`, the path `1 -> 2 -> 0 -> 3` uses three edges. The endpoint values differ by nine, and each edge changes the value by at most three, so fewer edges cannot suffice. Nodes `4` and `0` have a direct edge, as do the distinct equal-valued nodes `2` and `4`. Node `5` is isolated. The last query needs no edges.
**Example 2**
```text
n = 4
nums = [6,2,6,2]
maxDiff = 0
queries = [[0,2],[1,3],[0,1],[2,2]]
Output: [1,1,-1,0]
```
Different nodes with equal values have an edge even at threshold zero. Nodes with values two and six are in separate groups. A node's distance to itself remains zero.
### Constraints
- `1 <= n == nums.length <= 100000`.
- `0 <= nums[i] <= 100000`; duplicate values are allowed.
- `0 <= maxDiff <= 100000`.
- `1 <= queries.length <= 100000`.
- Each query is `[u, v]` with `0 <= u, v < n`.
- Queries do not change the graph.
### Clarifying Questions
- Does distance mean the sum of value differences? No. Every edge has weight one; distance counts edges.
- Are query endpoints array positions or values? They are the original node indices, even when values repeat.
- Must a path use nodes in their original array order? No. The graph's edge rule imposes no such restriction.
- Is a direct edge required for a finite answer? No. Paths may use intermediate nodes.
### What a Strong Answer Covers
- Exact minimum edge counts, with separate treatment of unreachable pairs and self-queries.
- Correct handling of unsorted values, repeated values, and zero thresholds.
- Preservation of original node identities and query order.
- A correctness argument and resource bounds for the full node and query limits.
### Follow-up Questions
- How can the distance between distinct equal-valued nodes differ from the distance of a node to itself?
- As `maxDiff` increases, can a finite minimum distance become larger? Explain from the allowed edges.
```hint Repeated reach
Sort node-value pairs while retaining the original index mapping. From each sorted position, find the farthest position to its right reachable in one edge. The farthest reachable position is monotone; use repeated doubling to count how many steps are needed to reach a query target.
```
Overview: Find minimum edge counts between original node labels in a graph defined by value differences. Handle unsorted and repeated values, unreachable pairs, and zero-length self paths.