What is the main approach for Path Existence Queries in a Graph I?

The problem is solved by grouping nodes into connected segments using array scanning, then using a hash table to map nodes to component IDs for fast query checks.

Can I use union-find for this problem?

Yes, union-find works, but for sorted arrays, array scanning with hash lookup is faster and simpler due to continuous segments.

How do I handle large queries efficiently?

Precompute component IDs for all nodes and use hash table lookups to answer each query in O(1) time.

What happens if maxDiff is zero?

Only nodes with identical nums values form segments, so connectivity is limited to repeated values.

Does sorting nums help in this problem?

Yes, sorted nums allows sequential scanning to detect segments and apply binary search to efficiently define component boundaries.

#3532

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

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

数组哈希表二分查找并查集图

题目描述

给你一个整数 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 之间是否存在路径。

返回一个布尔数组 answer，其中 answer[i] 等于 true 表示在第 i 个查询中节点 u_i 和 v_i 之间存在路径，否则为 false。

示例 1：

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

输出: [true,false]

解释:

查询 [0,0]：节点 0 有一条到自己的显然路径。
查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |1 - 3| = 2，大于 maxDiff。
因此，在处理完所有查询后，最终答案为 [true, false]。

示例 2：

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

输出: [false,false,true,true]

解释:

生成的图如下：

查询 [0,1]：节点 0 和节点 1 之间没有边，因为 |nums[0] - nums[1]| = |2 - 5| = 3，大于 maxDiff。
查询 [0,2]：节点 0 和节点 2 之间没有边，因为 |nums[0] - nums[2]| = |2 - 6| = 4，大于 maxDiff。
查询 [1,3]：节点 1 和节点 3 之间存在路径通过节点 2，因为 |nums[1] - nums[2]| = |5 - 6| = 1 和 |nums[2] - nums[3]| = |6 - 8| = 2，都小于等于 maxDiff。
查询 [2,3]：节点 2 和节点 3 之间有一条边，因为 |nums[2] - nums[3]| = |6 - 8| = 2，等于 maxDiff。
因此，在处理完所有查询后，最终答案为 [false, false, true, true]。

提示：

1 <= n == nums.length <= 10⁵
0 <= nums[i] <= 10⁵
nums 按 非递减 顺序排序。
0 <= maxDiff <= 10⁵
1 <= queries.length <= 10⁵
queries[i] == [u_i, v_i]
0 <= u_i, v_i < n

lightbulb

解题思路

方法一：分组

根据题目描述，同一个连通分量的节点编号，一定是连续的。因此，我们可以用一个数组 $g$ 来记录每个节点所在的连通分量编号，用一个变量 $\textit{cnt}$ 来记录当前连通分量的编号。遍历 $\textit{nums}$ 数组，如果当前节点和前一个节点的差值大于 $\textit{maxDiff}$ ，则说明当前节点和前一个节点不在同一个连通分量中，我们就将 $\textit{cnt}$ 加 1。然后，我们将当前节点的连通分量编号赋值为 $\textit{cnt}$ 。

最后，对于每个查询 $(u, v)$ ，我们只需要判断 $g[u]$ 和 $g[v]$ 是否相等即可，如果相等，则说明 $u$ 和 $v$ 在同一个连通分量中，那么第 $i$ 个查询的答案就是 $\text{true}$ ，否则就是 $\text{false}$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是 $\textit{nums}$ 数组的长度。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def pathExistenceQueries(
        self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]
    ) -> List[bool]:
        g = [0] * n
        cnt = 0
        for i in range(1, n):
            if nums[i] - nums[i - 1] > maxDiff:
                cnt += 1
            g[i] = cnt
        return [g[u] == g[v] for u, v in queries]

speed

复杂度分析

指标	值
时间	complexity is O(n + q) for scanning and query lookup, with n being array length and q being number of queries. Space complexity is O(n) to store component IDs in the hash table.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for continuous segments in nums where differences are within maxDiff.
question_mark
Consider mapping nodes to components instead of exploring the graph for each query.
question_mark
Check if queries access the same or different segments efficiently.

warning

常见陷阱

外企场景

error
Failing to account for multiple consecutive nodes forming a segment.
error
Using repeated graph traversal per query instead of precomputed components.
error
Not handling edge cases where maxDiff is zero or very large correctly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow dynamic updates to nums and handle incremental queries.
arrow_right_alt
Find the minimum maxDiff required to connect two given nodes.
arrow_right_alt
Support weighted edges where difference contributes to edge cost and queries check reachability within a threshold.

help

常见问题

外企场景

继续练习

#3493 属性图 #3607 电网维护 #3534 针对图的路径存在性查询 II