Reachability Queries in a Value-Difference Graph

# Reachability Queries in a Value-Difference Graph There are `n` graph nodes labeled `0` through `n - 1`. You are given their integer values in an array `nums`, already sorted in non-decreasing order, and a nonnegative integer `maxDiff`. Nodes `i` and `j` have an undirected edge exactly when `abs(nums[i] - nums[j]) <= maxDiff`. For every pair `[u, v]` in `queries`, return whether a path exists from `u` to `v`. A node has a path of length zero to itself. Return a boolean array in query order. ### C++ Interface ```cpp class Solution { public: vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries); }; ``` ### Examples **Example 1** ```text n = 6 nums = [0,0,3,5,8,8] maxDiff = 2 queries = [[0,1],[1,2],[2,3],[3,4],[4,5],[5,5]] Output: [true,false,true,false,true,true] ``` Nodes `0` and `1` share value zero; nodes `2` and `3` differ by two; nodes `4` and `5` share value eight. These are three separate connected groups. The last query stays at the same node. **Example 2** ```text n = 4 nums = [1,3,5,7] maxDiff = 2 queries = [[0,3],[3,0],[1,1]] Output: [true,true,true] ``` The path `0 -> 1 -> 2 -> 3` connects the endpoints even though their values differ by more than `maxDiff`. Edges are undirected, so the reversed query is also true. ### Constraints - `1 <= n == nums.length <= 100000`. - `0 <= nums[i] <= 100000`. - `nums` is sorted in non-decreasing order; duplicate values are allowed. - `0 <= maxDiff <= 100000`. - `1 <= queries.length <= 100000`. - Each query is `[u, v]` with `0 <= u, v < n`. ### Clarifying Questions - Must the queried nodes have a direct edge? No. A path may pass through other nodes. - Can two different nodes have equal values? Yes; their difference is zero. - Do the queries modify the values or the graph? No. Every query refers to the same graph. - What happens for `[u, u]`? The answer is always true, including when the node has no neighbors. ### What a Strong Answer Covers - The difference between a direct edge and a path with intermediate nodes. - Accurate answers for repeated values, isolated nodes, and zero thresholds. - Preservation of the original node labels and query order. - A justified running time and memory bound for up to `100000` nodes and queries. ### Follow-up Questions - How do the answers change when `maxDiff` is zero? - Can increasing `maxDiff` make any previously true answer become false? Explain using the graph definition. ```hint Use the sorted input A gap larger than maxDiff between consecutive values prevents every edge from crossing that gap. Consecutive values separated by smaller gaps can be linked into a path. Label the resulting connected components once. ```