Given an undirected graph with N nodes, labeled from 0 to N - 1.

You are given a 0-indexed sorted integer array arr.

There is an edge between node i and node j if:

|arr[i] - arr[j]| <= diff

Implement a function:

func(arr, diff, queries)

Where queries is a list of pairs:

[u, v]

For each query [u, v], determine whether node u and node v are connected in the graph.

Example

N = 4
arr = [1, 2, 3, 6]
diff = 2
queries = [[0, 2], [1, 3]]

Output

[true, false]

这道题可以理解为：

给一个已排序数组 arr，每个下标是图里的一个节点。
如果两个位置 i, j 满足：

|arr[i] - arr[j]| <= diff

那么节点 i 和 j 之间有一条无向边。

现在给多个查询 [u, v]，判断两个节点是否连通。

例如：

N = 4
arr = [1, 2, 3, 6]
diff = 2
queries = [[0,2], [1,3]]

节点 0,1,2 可以互相连通，因为：

1 和 2 差 1
2 和 3 差 1
1 和 3 差 2

但 6 跟前面的数字差距太大，所以节点 3 单独在另一个连通块里。

所以结果是：

[true, false]

这题的关键不是暴力建图。
因为 arr 已经排序，只需要看相邻元素之间的差值。

如果：

arr[i] - arr[i-1] <= diff

说明 i 和 i-1 在同一个连通块。
否则从这里断开，进入新的连通块。

预处理每个下标属于哪个 group，之后每个 query 只需要判断：

group[u] == group[v]

时间复杂度：

预处理 O(N)
每个查询 O(1)
总复杂度 O(N + Q)

这是一道很典型的 Google 面试题，表面是图，实际考察的是能不能利用 sorted array 的性质，把图连通性问题转化成区间分组问题。

CSOAHelp 面试辅助中，我们会帮助候选人快速识别这类题目的隐藏结构，整理最优解思路，并用面试官能接受的表达方式完成讲解、代码和复杂度分析。

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~