147. Undirected Graph Path Queries

Undirected Graph Path Queries

You are given a list of integers arr of size N, and an integer diff.

Consider an undirected graph where each node corresponds to one index of arr.

Add an edge between nodes i and j if |arr[i] - arr[j]| ≤ diff.

You are also given a list of queries queries, where each query is a comma-separated string "u,v". For each query, return whether there is a path between node u and node v.

A path may use zero or more intermediate nodes.

Example: arr = [1, 2, 3, 6], diff = 2, queries = ["0,2", "1,3"] returns [true, false].

Method Signature

List<Boolean> pathQueries(List<Integer> arr, int diff, List<String> queries)

Parameters

arr is the input list of integers.
diff is the maximum allowed absolute difference for adding an undirected edge.
queries is a list of comma-separated strings, where each string is in the format "u,v".

Return Value

Return a List<Boolean>.
The answer at position k corresponds to the query at position k in queries.
Return true if there is a path between the two queried indices, otherwise return false.

Constraints

1 ≤ N ≤ 10^5
0 ≤ diff ≤ 10^9
-10^9 ≤ arr[i] ≤ 10^9
1 ≤ queries.size() ≤ 10^5
Each query string must contain exactly two valid comma-separated integers u and v.
For every query "u,v", 0 ≤ u < N and 0 ≤ v < N.
arr may contain duplicate values.
You must never use null as a parameter value.

Notes

The graph is undirected.
A node is always reachable from itself.
The path for a query may use intermediate indices.
arr may be sorted in non-decreasing order, sorted in non-increasing order, or unsorted.
If you sort internally to solve the problem efficiently, queries must still refer to the original indices of arr.

Examples

Example 1

pathQueries(arr = List.of(1, 2, 3, 6), diff = 2, queries = List.of("0,2", "1,3"))

returns List.of(true, false)

Explanation:

Indices 0 and 2 are directly connected because |1 - 3| = 2, so the first answer is true.
Indices 1 and 3 are not directly connected, and no intermediate path exists, so the second answer is false.

Example 2

pathQueries(arr = List.of(6, 3, 2, 1), diff = 2, queries = List.of("0,1", "1,3", "0,3"))

returns List.of(false, true, false)

Explanation:

Index 0 has value 6 and is not connected to any other index because all absolute differences are greater than 2.
Indices 1 and 3 are directly connected because |3 - 1| = 2.
Since index 0 is isolated, "0,3" also returns false.

Example 3

pathQueries(arr = List.of(3, 1, 6, 2), diff = 1, queries = List.of("1,3", "0,2", "0,1"))

returns List.of(true, false, true)

Explanation:

Indices 1 and 3 are directly connected because |1 - 2| = 1.
Index 2 has value 6 and is isolated here, so "0,2" returns false.
Indices 0 and 1 are connected through index 3.