How do I approach the 'Path Existence Queries in a Graph II' problem?

Start by sorting the nodes based on their values in `nums` and use binary search to check the path existence. Union-find will help efficiently manage connectivity between nodes.

What is the time complexity of this problem?

The time complexity is O(n log n + q), where `n` is the number of nodes and `q` is the number of queries, due to sorting and union-find operations.

Can this problem be solved with a brute force approach?

While a brute force approach may work, it would be inefficient for large inputs, especially with many queries. Binary search and union-find are essential for optimal performance.

What role does the maximum difference `maxDiff` play in this problem?

The `maxDiff` value determines whether an edge exists between two nodes. Only nodes with values whose difference is less than or equal to `maxDiff` can be connected.

How does GhostInterview help with this problem?

GhostInterview walks through sorting the nodes, applying binary search, and using union-find to ensure efficient answers to path existence queries.

#3534

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

针对图的路径存在性查询 II

给你一个整数 n ，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。同时给你一个长度为 n 的整数数组 nums ，以及一个整数 maxDiff 。如果满足 |nums[i] - nums[j]| （即 nums[i] 和 nums[j] 的绝对差至多为 maxDiff ），则节…

数组二分查找贪心图排序

题目描述

给你一个整数 n，表示图中的节点数量，这些节点按从 0 到 n - 1 编号。

同时给你一个长度为 n 的整数数组 nums，以及一个整数 maxDiff。

如果满足 |nums[i] - nums[j]| <= maxDiff（即 nums[i] 和 nums[j] 的 绝对差 至多为 maxDiff），则节点 i 和节点 j 之间存在一条 无向边 。

此外，给你一个二维整数数组 queries。对于每个 queries[i] = [u_i, v_i]，找到节点 u_i 和节点 v_i 之间的 最短距离 。如果两节点之间不存在路径，则返回 -1。

返回一个数组 answer，其中 answer[i] 是第 i 个查询的结果。

注意：节点之间的边是无权重（unweighted）的。

示例 1：

输入: n = 5, nums = [1,8,3,4,2], maxDiff = 3, queries = [[0,3],[2,4]]

输出: [1,1]

解释:

生成的图如下：

查询	最短路径	最短距离
[0, 3]	0 → 3	1
[2, 4]	2 → 4	1

因此，输出为 [1, 1]。

示例 2：

输入: n = 5, nums = [5,3,1,9,10], maxDiff = 2, queries = [[0,1],[0,2],[2,3],[4,3]]

输出: [1,2,-1,1]

解释:

生成的图如下：

查询	最短路径	最短距离
[0, 1]	0 → 1	1
[0, 2]	0 → 1 → 2	2
[2, 3]	无	-1
[4, 3]	3 → 4	1

因此，输出为 [1, 2, -1, 1]。

示例 3：

输入: n = 3, nums = [3,6,1], maxDiff = 1, queries = [[0,0],[0,1],[1,2]]

输出: [0,-1,-1]

解释:

由于以下原因，任意两个节点之间都不存在边：

节点 0 和节点 1：|nums[0] - nums[1]| = |3 - 6| = 3 > 1
节点 0 和节点 2：|nums[0] - nums[2]| = |3 - 1| = 2 > 1
节点 1 和节点 2：|nums[1] - nums[2]| = |6 - 1| = 5 > 1

因此，不存在任何可以到达其他节点的节点，输出为 [0, -1, -1]。

提示：

1 <= n == nums.length <= 10⁵
0 <= nums[i] <= 10⁵
0 <= maxDiff <= 10⁵
1 <= queries.length <= 10⁵
queries[i] == [u_i, v_i]
0 <= u_i, v_i < n

lightbulb

解题思路

方法一

1

2

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidates should demonstrate familiarity with binary search and union-find techniques.
question_mark
The ability to efficiently handle large input sizes and multiple queries is a key indicator of success.
question_mark
Look for candidates who can clearly explain the reasoning behind sorting nodes and applying binary search.

warning

常见陷阱

外企场景

error
Failure to sort nodes properly before applying binary search can lead to incorrect results.
error
Not using the union-find structure efficiently may result in time complexity issues for large inputs.
error
Candidates may struggle with the time complexity of large numbers of queries and nodes if they don't optimize the solution properly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider varying the `maxDiff` value to test different graph connectivity scenarios.
arrow_right_alt
Test edge cases with a minimal number of nodes and queries to ensure robustness.
arrow_right_alt
Introduce additional constraints such as larger arrays or more complex queries to challenge performance.

help

常见问题

外企场景

继续练习

#3413 收集连续 K 个袋子可以获得的最多硬币数量 #3281 范围内整数的最大得分 #2967 使数组成为等数数组的最小代价