Path Existence Queries in a Graph II

Problem summary

We have n nodes with values nums, and an undirected edge connects any two nodes i and j whenever |nums[i] - nums[j]| <= maxDiff. Unlike Part I, nums is not given sorted, and each query now asks for the minimum number of edges on a path between u and v (or -1 if they are disconnected).

Both n and the number of queries go up to 10^5. A BFS per query is O(q · (n + edges)), and the graph can have O(n^2) edges, so that is hopelessly slow. We need to preprocess once and then answer each query in roughly O(log n).

Step 1: sort by value, so an edge becomes a window

The edge rule only cares about values, not positions. So sort the nodes by their value. After sorting, look at any node at sorted position i. The nodes it can reach in one edge are exactly those whose value lies within maxDiff of nums[i] — and because the array is now sorted, those form a contiguous window around i:

... [ lo  ...  i  ...  hi ] ...
        \_______________/
     every value here is within maxDiff of nums[i]

That is the whole reason we sort: a messy graph turns into a clean "each index can jump to a contiguous range" structure — a one-dimensional jump game.

We keep two small maps:

• sorted[i] — the (value, original index) sitting at sorted position i
• pos[original index] — the reverse map, so a query on original nodes becomes a query on sorted positions

Step 2: the farthest right you can jump

To travel from a smaller position a to a larger position b, you only ever need to move right. And to move right in the fewest hops, you always want to jump as far right as possible — this is the classic greedy for the jump game.

So for every position i, precompute:

st[i][0] = the farthest sorted index r such that nums[r] - nums[i] <= maxDiff

Since values are sorted, this right boundary only moves forward as i increases, so a two-pointer sweep computes all of them in a single O(n) pass — no binary search per index needed.

r = 0
for i in 0 .. n-1:
    r = max(r, i)
    while r+1 < n and sorted[r+1].val - sorted[i].val <= maxDiff:
        r++
    st[i][0] = r

Step 3: binary lifting to jump many steps at once

If we followed st[·][0] one hop at a time we could take O(n) hops per query — too slow. Instead we use binary lifting (the same doubling trick used for the k-th ancestor in a tree).

Define st[i][j] = the farthest index reachable from i using 2^j jumps. Each level is built from the one below it in O(1):

st[i][j] = st[ st[i][j-1] ][j-1]

"Jump 2^j steps" = "jump 2^(j-1) steps, then 2^(j-1) more." With LOG = 18 levels we cover up to 2^17 > 10^5 jumps, so any distance fits.

Step 4: answering a query

For a query, convert both endpoints to sorted positions a and b and make a <= b (the graph is undirected, so direction does not matter). If a == b, the distance is 0.

Otherwise, greedily jump from a as far right as we can without reaching or passing b, using the lifting table from the highest level down:

curr = a, steps = 0
for j from LOG-1 down to 0:
    if st[curr][j] < b:      # jump only if we stay strictly left of b
        curr = st[curr][j]
        steps += 2^j

After this loop curr is the farthest position < b we can land on, and steps is how many hops it took. Now just check whether one more hop covers b:

if st[curr][0] >= b:   answer = steps + 1
else:                  answer = -1

Why does the final check catch the -1 case? st[curr][0] >= b means nums[b] - nums[curr] <= maxDiff, i.e. there is a direct edge curr → b, so we finish in one last hop. If instead st[curr][0] < b, then curr is the right end of its connected segment and b sits beyond a gap that no edge can cross — the two nodes are in different components, so the answer is -1. (In that disconnected case the greedy loop keeps "jumping" onto the segment's end and inflates steps, but that value is thrown away — only the final reachability check decides the result.)

class Solution {
    public int[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        final int LOG = 18;

        // Pair each value with its original index, then sort by value.
        int[][] sorted = new int[n][2];
        for (int i = 0; i < n; i++) sorted[i] = new int[]{nums[i], i};
        Arrays.sort(sorted, (a, b) -> a[0] - b[0]);

        // pos[original index] = where that node sits in sorted order.
        int[] pos = new int[n];
        for (int i = 0; i < n; i++) pos[sorted[i][1]] = i;

        // st[i][0] = farthest sorted index directly reachable to the right of i.
        int[][] st = new int[n][LOG];
        int r = 0;
        for (int i = 0; i < n; i++) {
            if (r < i) r = i;
            while (r + 1 < n && sorted[r + 1][0] - sorted[i][0] <= maxDiff) r++;
            st[i][0] = r;
        }

        // Binary lifting: st[i][j] = farthest index reachable from i in 2^j jumps.
        for (int j = 1; j < LOG; j++)
            for (int i = 0; i < n; i++)
                st[i][j] = st[st[i][j - 1]][j - 1];

        int[] ans = new int[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int a = pos[queries[q][0]];
            int b = pos[queries[q][1]];
            if (a > b) { int t = a; a = b; b = t; }
            if (a == b) { ans[q] = 0; continue; }

            int curr = a, steps = 0;
            for (int j = LOG - 1; j >= 0; j--) {
                if (st[curr][j] < b) {
                    curr = st[curr][j];
                    steps += (1 << j);
                }
            }
            ans[q] = (st[curr][0] >= b) ? steps + 1 : -1;
        }
        return ans;
    }
}

Walkthrough

Take Example 2:

n = 5, nums = [5, 3, 1, 9, 10], maxDiff = 2
queries = [[0,1], [0,2], [2,3], [4,3]]

Sort by value

sorted position:   0   1   2   3   4
value:             1   3   5   9  10
original node:     2   1   0   3   4

So pos[node 2]=0, pos[node 1]=1, pos[node 0]=2, pos[node 3]=3, pos[node 4]=4.

Farthest one-hop reach st[i][0]

i=0 (val 1):  3-1=2 ✔, 5-1=4 ✗ stop      -> st[0][0] = 1
i=1 (val 3):  5-3=2 ✔, 9-3=6 ✗ stop      -> st[1][0] = 2
i=2 (val 5):  9-5=4 ✗ stop               -> st[2][0] = 2
i=3 (val 9): 10-9=1 ✔                     -> st[3][0] = 4
i=4 (val 10): (end)                       -> st[4][0] = 4

The graph splits into two contiguous components:

[ 1, 3, 5 ]        [ 9, 10 ]
 pos 0,1,2          pos 3,4

Query [0, 1] → positions a=2, b=1 → swap to a=1, b=2

st[1][0] = 2 is not < 2, so no jump is taken. Final check st[1][0] = 2 >= 2 → 1.

Query [0, 2] → positions a=2, b=0 → swap to a=0, b=2

Higher levels all land on 2 (not < 2), so they are skipped. At j=0, st[0][0] = 1 < 2 → jump to curr=1, steps=1. Final check st[1][0] = 2 >= 2 → steps + 1 = 2.

Query [2, 3] → positions a=0, b=3

a=0 is in the first component whose far end is position 2. The greedy loop walks curr to 2 (the segment's end). Final check st[2][0] = 2 >= 3? No → -1.

Query [4, 3] → positions a=4, b=3 → swap to a=3, b=4

st[3][0] = 4 is not < 4, so no jump. Final check st[3][0] = 4 >= 4 → 1.

Final answer: [1, 2, -1, 1].

Complexity analysis

Time Complexity: O((n + q) log n)

• sorting is O(n log n)
• the two-pointer sweep is O(n); the lifting table has n · LOG entries, each filled in O(1)
• each of the q queries scans LOG levels, so O(log n) per query

Space Complexity: O(n log n)

For the binary-lifting table st of size n · LOG.

Common mistakes

1. Running a BFS per query

The graph can have O(n^2) edges, so even one BFS can be O(n^2). With up to 10^5 queries this times out badly. Preprocess once instead.

2. Forgetting to map back to sorted positions

All the jump logic lives in sorted order, but queries reference original node indices. You must translate each endpoint through pos[] before jumping, or you will compare the wrong positions.

3. Treating the answer as "reach position ≥ b" without the direct-edge insight

It works only because st[curr][0] >= b guarantees a real edge curr → b (all values between curr and st[curr][0] are within maxDiff). This is why we can stop the moment one hop covers b, instead of insisting on landing exactly on b mid-way.

4. Mis-detecting disconnection

When u and v are in different components, the greedy loop still "jumps" and inflates steps. Do not return steps + 1 blindly — the st[curr][0] >= b check is what distinguishes a real final hop from a dead end that must return -1.

5. Too few lifting levels

LOG must satisfy 2^(LOG-1) >= n. For n up to 10^5, LOG = 17 is the minimum and 18 is a safe choice. Using too few levels silently caps the reachable distance and produces wrong answers on long chains.