3534. Path Existence Queries in a Graph II Hard

1/**
2 * [3534] Path Existence Queries in a Graph II
3 *
4 * You are given an integer n representing the number of nodes in a graph, labeled from 0 to n - 1.
5 * You are also given an integer array nums of length n and an integer maxDiff.
6 * 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).
7 * 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.
8 * Return an array answer, where answer[i] is the result of the i^th query.
9 * Note: The edges between the nodes are unweighted.
10 *  
11 * <strong class="example">Example 1:
12 * <div class="example-block">
13 * Input: <span class="example-io">n = 5, nums = [1,8,3,4,2], maxDiff = 3, queries = [[0,3],[2,4]]</span>
14 * Output: <span class="example-io">[1,1]</span>
15 * Explanation:
16 * The resulting graph is:
17 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/25/4149example1drawio.png" style="width: 281px; height: 161px;" />
18 * <table>
19 * 	<tbody>
20 * 		<tr>
21 * 			<th>Query</th>
22 * 			<th>Shortest Path</th>
23 * 			<th>Minimum Distance</th>
24 * 		</tr>
25 * 		<tr>
26 * 			<td>[0, 3]</td>
27 * 			<td>0 &rarr; 3</td>
28 * 			<td>1</td>
29 * 		</tr>
30 * 		<tr>
31 * 			<td>[2, 4]</td>
32 * 			<td>2 &rarr; 4</td>
33 * 			<td>1</td>
34 * 		</tr>
35 * 	</tbody>
36 * </table>
37 * Thus, the output is [1, 1].
38 * </div>
39 * <strong class="example">Example 2:
40 * <div class="example-block">
41 * Input: <span class="example-io">n = 5, nums = [5,3,1,9,10], maxDiff = 2, queries = [[0,1],[0,2],[2,3],[4,3]]</span>
42 * Output: <span class="example-io">[1,2,-1,1]</span>
43 * Explanation:
44 * The resulting graph is:
45 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/25/4149example2drawio.png" style="width: 281px; height: 121px;" />
46 * </div>
47 * <table>
48 * 	<tbody>
49 * 		<tr>
50 * 			<th>Query</th>
51 * 			<th>Shortest Path</th>
52 * 			<th>Minimum Distance</th>
53 * 		</tr>
54 * 		<tr>
55 * 			<td>[0, 1]</td>
56 * 			<td>0 &rarr; 1</td>
57 * 			<td>1</td>
58 * 		</tr>
59 * 		<tr>
60 * 			<td>[0, 2]</td>
61 * 			<td>0 &rarr; 1 &rarr; 2</td>
62 * 			<td>2</td>
63 * 		</tr>
64 * 		<tr>
65 * 			<td>[2, 3]</td>
66 * 			<td>None</td>
67 * 			<td>-1</td>
68 * 		</tr>
69 * 		<tr>
70 * 			<td>[4, 3]</td>
71 * 			<td>3 &rarr; 4</td>
72 * 			<td>1</td>
73 * 		</tr>
74 * 	</tbody>
75 * </table>
76 * Thus, the output is [1, 2, -1, 1].
77 * <strong class="example">Example 3:
78 * <div class="example-block">
79 * Input: <span class="example-io">n = 3, nums = [3,6,1], maxDiff = 1, queries = [[0,0],[0,1],[1,2]]</span>
80 * Output: <span class="example-io">[0,-1,-1]</span>
81 * Explanation:
82 * There are no edges between any two nodes because:
83 * 
84 * 	Nodes 0 and 1: |nums[0] - nums[1]| = |3 - 6| = 3 > 1
85 * 	Nodes 0 and 2: |nums[0] - nums[2]| = |3 - 1| = 2 > 1
86 * 	Nodes 1 and 2: |nums[1] - nums[2]| = |6 - 1| = 5 > 1
87 * 
88 * Thus, no node can reach any other node, and the output is [0, -1, -1].
89 * </div>
90 *  
91 * Constraints:
92 * 
93 * 	1 <= n == nums.length <= 10^5
94 * 	0 <= nums[i] <= 10^5
95 * 	0 <= maxDiff <= 10^5
96 * 	1 <= queries.length <= 10^5
97 * 	queries[i] == [ui, vi]
98 * 	0 <= ui, vi < n
99 * 
100 */
101pub struct Solution {}
102
103// problem: https://leetcode.com/problems/path-existence-queries-in-a-graph-ii/
104// discuss: https://leetcode.com/problems/path-existence-queries-in-a-graph-ii/discuss/?currentPage=1&orderBy=most_votes&query=
105
106// submission codes start here
107
108impl Solution {
109    pub fn path_existence_queries(n: i32, nums: Vec<i32>, max_diff: i32, queries: Vec<Vec<i32>>) -> Vec<i32> {
110        vec![]
111    }
112}
113
114// submission codes end
115
116#[cfg(test)]
117mod tests {
118    use super::*;
119
120    #[test]
121    fn test_3534() {
122    }
123}
124