Show problems as
Classic problem #3532MediumArrayHash TableBinary SearchUnion-FindGraph Theory

Path Existence Queries in a Graph I

Real-world version: Sync Reachability Across Calibration Bands
Tracked in this browser only
Read Path Existence Queries in a Graph I on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A rack holds n instruments numbered 0 to n - 1. Instrument i reports the calibration reading nums[i], and the readings are handed over already sorted in non-decreasing order.

Two instruments can talk to each other directly when their readings sit within maxDiff of one another, that is when abs(nums[i] - nums[j]) <= maxDiff. A calibration signal may also be relayed: it travels from one instrument to another whenever some chain of direct links connects them, with any number of hops in between.

Each entry of queries is a pair [u, v]. Return an array of booleans, one per query in the same order, saying whether a signal can get from instrument u to instrument v. An instrument can always reach itself.

Examples

Example 1

Input
n = 5, nums = [2, 3, 4, 6, 9], maxDiff = 2, queries = [[0, 3], [0, 4], [4, 4], [3, 4]]
Output
[true, false, true, false]

Readings 2, 3, 4 and 6 form one relay chain because each neighbouring step is 1, 1 and 2. The reading 9 is 3 above 6 and further from the rest, so nothing links it, and a query onto itself is still true.

Example 2

Input
n = 3, nums = [5, 5, 7], maxDiff = 0, queries = [[0, 1], [1, 2], [0, 2]]
Output
[true, false, false]

Only identical readings can talk when maxDiff is 0, so instruments 0 and 1 are linked and instrument 2 stands alone.

Example 3

Input
n = 3, nums = [0, 10, 20], maxDiff = 10, queries = [[0, 2], [0, 1]]
Output
[true, true]

Instrument 0 links to 1 and 1 links to 2, each step being exactly 10, so a relayed signal covers 0 to 2 even though their own readings differ by 20.

Example 4

Input
n = 6, nums = [0, 1, 7, 8, 9, 40], maxDiff = 3, queries = [[0, 1], [0, 2], [2, 4], [4, 5]]
Output
[true, false, true, false]

Instruments 0 and 1 sit together with a step of 1. Instruments 2, 3 and 4 form a second group, their neighbouring steps being 1 and 1. Instrument 5 reads 40, which is 31 above its nearest neighbour, so it links to nothing.

Constraints

  • 1 <= n == nums.length <= 10^5
  • 0 <= nums[i] <= 10^5
  • nums is sorted in non-decreasing order.
  • 0 <= maxDiff <= 10^5
  • 1 <= queries.length <= 10^5
  • queries[i] == [u_i, v_i]
  • 0 <= u_i, v_i < n

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def sync_reachability(count: int, readings: list[int], max_gap: int, pairs: list[list[int]]) -> list[bool]:
Java
public boolean[] syncReachability(int count, int[] readings, int maxGap, int[][] pairs)

More on the same topics