3532. Path Existence Queries in a Graph I Medium

1/**
2 * [3532] Path Existence Queries in a Graph I
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 sorted in non-decreasing order, 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], determine whether there exists a path between nodes ui and vi.
8 * Return a boolean array answer, where answer[i] is true if there exists a path between ui and vi in the i^th query and false otherwise.
9 *  
10 * <strong class="example">Example 1:
11 * <div class="example-block">
12 * Input: <span class="example-io">n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]</span>
13 * Output: <span class="example-io">[true,false]</span>
14 * Explanation:
15 * 
16 * 	Query [0,0]: Node 0 has a trivial path to itself.
17 * 	Query [0,1]: There is no edge between Node 0 and Node 1 because |nums[0] - nums[1]| = |1 - 3| = 2, which is greater than maxDiff.
18 * 	Thus, the final answer after processing all the queries is [true, false].
19 * </div>
20 * <strong class="example">Example 2:
21 * <div class="example-block">
22 * Input: <span class="example-io">n = 4, nums = [2,5,6,8], maxDiff = 2, queries = [[0,1],[0,2],[1,3],[2,3]]</span>
23 * Output: <span class="example-io">[false,false,true,true]</span>
24 * Explanation:
25 * The resulting graph is:
26 * <img alt="" src="https://assets.leetcode.com/uploads/2025/03/25/screenshot-2025-03-26-at-122249.png" style="width: 300px; height: 170px;" />
27 * 
28 * 	Query [0,1]: There is no edge between Node 0 and Node 1 because |nums[0] - nums[1]| = |2 - 5| = 3, which is greater than maxDiff.
29 * 	Query [0,2]: There is no edge between Node 0 and Node 2 because |nums[0] - nums[2]| = |2 - 6| = 4, which is greater than maxDiff.
30 * 	Query [1,3]: There is a path between Node 1 and Node 3 through Node 2 since |nums[1] - nums[2]| = |5 - 6| = 1 and |nums[2] - nums[3]| = |6 - 8| = 2, both of which are within maxDiff.
31 * 	Query [2,3]: There is an edge between Node 2 and Node 3 because |nums[2] - nums[3]| = |6 - 8| = 2, which is equal to maxDiff.
32 * 	Thus, the final answer after processing all the queries is [false, false, true, true].
33 * </div>
34 *  
35 * Constraints:
36 * 
37 * 	1 <= n == nums.length <= 10^5
38 * 	0 <= nums[i] <= 10^5
39 * 	nums is sorted in non-decreasing order.
40 * 	0 <= maxDiff <= 10^5
41 * 	1 <= queries.length <= 10^5
42 * 	queries[i] == [ui, vi]
43 * 	0 <= ui, vi < n
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/path-existence-queries-in-a-graph-i/
49// discuss: https://leetcode.com/problems/path-existence-queries-in-a-graph-i/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn path_existence_queries(n: i32, nums: Vec<i32>, max_diff: i32, queries: Vec<Vec<i32>>) -> Vec<bool> {
55        
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_3532() {
67    }
68}
69