Path Existence Queries in a Graph I

Problem summary

We have n nodes labeled 0 to n - 1, an array nums sorted in non-decreasing order, and a value maxDiff. There is an undirected edge between nodes i and j whenever |nums[i] - nums[j]| <= maxDiff.

For each query [u, v] we must report whether a path connects u and v.

With both n and the number of queries up to 10^5, we cannot build the full graph (it can have up to O(n^2) edges) or run a fresh BFS per query. We need something close to O(1) per query after preprocessing.

Key observation: sorted means only neighbours matter

The whole trick lives in the word sorted. Because nums is non-decreasing, for any i < j:

nums[j] - nums[i] = (nums[i+1] - nums[i]) + (nums[i+2] - nums[i+1]) + ... + (nums[j] - nums[j-1])

Every term on the right is >= 0, so the distance between two nodes is at least the distance between any adjacent pair between them. That gives two facts:

• If two adjacent nodes i and i + 1 satisfy nums[i+1] - nums[i] <= maxDiff, they are directly connected.
• If some adjacent gap in [i, j] exceeds maxDiff, then nums[j] - nums[i] also exceeds maxDiff, and — more importantly — that gap is a wall that nothing can cross: no node on the left of the wall can reach any node on its right.

So the graph collapses into contiguous groups. A group is a maximal run of consecutive indices where every adjacent gap is <= maxDiff. Two nodes are in the same component iff no oversized gap sits between them. We never need a non-adjacent edge — they are all redundant.

Building the components

The cleanest way to express "same contiguous group" is a Disjoint Set Union (Union-Find). Walk once over the array and union i with i + 1 whenever their gap fits:

for i in 0 .. n-2:
    if |nums[i] - nums[i+1]| <= maxDiff:
        union(i, i+1)

Since the array is sorted the absolute value is optional (nums[i+1] >= nums[i]), but keeping abs makes the code robust and matches the edge definition literally.

After this single pass, each connected run shares one DSU root. A query [u, v] is then just a root comparison:

answer = find(u) == find(v)

A node is trivially connected to itself, and find(u) == find(u) returns true for free, so the [u, u] case needs no special handling.

Full approach

1. Initialise a DSU over n nodes.
2. For each i from 0 to n - 2, union i and i + 1 if |nums[i] - nums[i+1]| <= maxDiff.
3. For each query [u, v], answer find(u) == find(v).

The DSU uses union by size plus path compression, so every find/union runs in near-constant amortised time (inverse Ackermann).

class Solution {
    public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        int m = queries.length;
        boolean[] answer = new boolean[m];

        DSU dsu = new DSU(n);

        for (int i = 0; i < n - 1; i++) {
            if (Math.abs(nums[i] - nums[i + 1]) <= maxDiff) {
                dsu.union(i, i + 1);
            }
        }

        for (int i = 0; i < m; i++) {
            int u = queries[i][0];
            int v = queries[i][1];
            answer[i] = dsu.find(u) == dsu.find(v);
        }
        return answer;
    }

    class DSU {
        int[] parent;
        int[] size;

        DSU(int n) {
            parent = new int[n];
            size = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        void union(int a, int b) {
            a = find(a);
            b = find(b);
            if (a == b) return;

            if (size[a] < size[b]) {
                int t = a;
                a = b;
                b = t;
            }

            parent[b] = a;
            size[a] += size[b];
        }

        int find(int x) {
            if (parent[x] == x) return x;
            return parent[x] = find(parent[x]);
        }
    }
}

Walkthrough

Take Example 2:

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

Check each adjacent gap:

i=0: |2 - 5| = 3 > 2   -> no union   (wall between 0 and 1)
i=1: |5 - 6| = 1 <= 2  -> union(1, 2)
i=2: |6 - 8| = 2 <= 2  -> union(2, 3)

Resulting components:

{0}        {1, 2, 3}

Now answer the queries by comparing roots:

[0,1]: find(0) != find(1)  -> false
[0,2]: find(0) != find(2)  -> false
[1,3]: find(1) == find(3)  -> true
[2,3]: find(2) == find(3)  -> true

Final answer: [false, false, true, true].

Complexity analysis

Time Complexity: O(n + q * α(n))

• one linear pass performs at most n - 1 unions
• each of the q queries is two find calls, each effectively O(1) amortised (α is the inverse Ackermann function)

Space Complexity: O(n)

For the DSU parent and size arrays.

Alternative: prefix component ids

Because the components are contiguous, you don't strictly need a DSU. Sweep once and assign each index a component id, bumping the id whenever an adjacent gap exceeds maxDiff:

id = 0
comp[0] = 0
for i in 1 .. n-1:
    if |nums[i] - nums[i-1]| > maxDiff: id++
    comp[i] = id

Then a query is simply comp[u] == comp[v]. This is O(n + q) with no inverse-Ackermann factor and even less code. The DSU version is shown as the main solution because it generalises to the harder follow-up problems where edges are not purely adjacency-based.

Common mistakes

1. Building the full graph

The edge rule connects every pair within maxDiff, which can be O(n^2) edges (imagine all equal values). Materialising that graph and running BFS per query blows both time and memory. Exploit the sorted order and only ever look at adjacent pairs.

2. Thinking non-adjacent edges can add connectivity

It is tempting to worry that i and i + 2 might connect even when i and i + 1 do not. On a sorted array that is impossible: if the i → i+1 gap is too big, the i → i+2 gap is at least as big. Adjacent gaps fully determine the components.

3. Off-by-one in the union loop

Union pairs (i, i + 1), so the loop must stop at i = n - 2. Running to n - 1 reads nums[n] out of bounds.

4. Forgetting the [u, u] / already-connected case

Every node reaches itself, and nodes in the same run reach each other. A plain find(u) == find(v) handles both automatically — no extra branch required.