3534. Path Existence Queries in a Graph II

Array
Binary Lifting
Sorting
Two Pointers
Greedy

TIME

O((n + q) log n)

SPACE

O(n log n)

Intuition

Sort the nodes by value. Then, exactly as in part I, connected components are contiguous runs in sorted order (a consecutive gap larger than maxDiff can't be crossed by any edge). Cross-component queries answer -1.

Within a component, a node at sorted index i connects to every node whose value lies in [val_i - maxDiff, val_i + maxDiff] a contiguous sorted range [L_i, R_i]. To reach a target on the right in the fewest hops, always jump as far right as possible. Because R_i is non-decreasing in i, the single most valuable jump from i lands exactly at R_i (that node's reach dominates every other choice in the range). This turns the shortest path into a classic greedy farthest-jump count, which binary lifting answers in O(log n) per query.

Approach

Sort node indices by nums; record each node's sorted rank and the sorted value array.
Two pointers compute R[i] = farthest sorted index reachable in one hop from i (largest j with val_j <= val_i + maxDiff).
Component ids via consecutive gaps (val_i - val_{i-1} > maxDiff starts a new component).
Binary-lifting table up[k][i] = position after 2^k greedy jumps, with up[0][i] = R[i].
Per query [u, v] with ranks su, sv (swap so su <= sv):
- Different components → -1.
- su == sv → 0.
- Otherwise binary-lift from su: for k high→low, if up[k][cur] < sv, take the jump (cur = up[k][cur], add 2^k). One final jump reaches sv, so answer is count + 1.

Complexity

Time: O((n + q) log n), sort, lifting table build, O(log n) per query
Space: O(n log n), the lifting table

Edge Cases

Self query [u, u] → 0
Isolated node (both neighbors' gaps exceed maxDiff) → only reaches itself
Duplicate values → all in one range, distance 1 between any two (or 0 if same node)
maxDiff = 0 → edges only between equal values
Same component always guarantees progress (R[i] > i for non-last nodes in a run), so the final +1 jump always lands

Code

from typing import List


class Solution:
    def pathExistenceQueries(self, n: int, nums: List[int], maxDiff: int, queries: List[List[int]]) -> List[int]:
        """
        3534. Path Existence Queries in a Graph II
        Time: O((n + q) log n)
        Space: O(n log n)
        """
        # Sort nodes by value; rank[node] = its position in sorted order.
        order = sorted(range(n), key=lambda i: nums[i])
        vals = [nums[i] for i in order]
        rank = [0] * n
        for k, node in enumerate(order):
            rank[node] = k

        # R[i] = farthest sorted index reachable in one hop from i.
        R = [0] * n
        j = 0
        for i in range(n):
            if j < i:
                j = i
            while j + 1 < n and vals[j + 1] - vals[i] <= maxDiff:
                j += 1
            R[i] = j

        # Component ids via consecutive gaps.
        comp = [0] * n
        for i in range(1, n):
            comp[i] = comp[i - 1] + (1 if vals[i] - vals[i - 1] > maxDiff else 0)

        # Binary lifting on the farthest-jump function.
        LOG = max(1, n.bit_length())
        up = [R]  # up[0]
        for _ in range(1, LOG):
            prev = up[-1]
            cur = [prev[prev[i]] for i in range(n)]
            up.append(cur)

        ans = []
        for u, v in queries:
            su, sv = rank[u], rank[v]
            if su > sv:
                su, sv = sv, su
            if su == sv:
                ans.append(0)
            elif comp[su] != comp[sv]:
                ans.append(-1)
            else:
                cur = su
                steps = 0
                for k in range(LOG - 1, -1, -1):
                    if up[k][cur] < sv:
                        cur = up[k][cur]
                        steps += 1 << k
                ans.append(steps + 1)  # one final jump reaches sv
        return ans

import java.util.Arrays;

/**
 * 3534. Path Existence Queries in a Graph II
 * Time: O((n + q) log n)
 * Space: O(n log n)
 */
class Solution {
    public int[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
        // Sort nodes by value; rank[node] = its position in sorted order.
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) {
            order[i] = i;
        }
        Arrays.sort(order, (a, b) -> nums[a] - nums[b]);
        int[] vals = new int[n];
        int[] rank = new int[n];
        for (int k = 0; k < n; k++) {
            vals[k] = nums[order[k]];
            rank[order[k]] = k;
        }

        // R[i] = farthest sorted index reachable in one hop from i.
        int[] R = new int[n];
        int j = 0;
        for (int i = 0; i < n; i++) {
            if (j < i) {
                j = i;
            }
            while (j + 1 < n && vals[j + 1] - vals[i] <= maxDiff) {
                j++;
            }
            R[i] = j;
        }

        // Component ids via consecutive gaps.
        int[] comp = new int[n];
        for (int i = 1; i < n; i++) {
            comp[i] = comp[i - 1] + (vals[i] - vals[i - 1] > maxDiff ? 1 : 0);
        }

        // Binary lifting on the farthest-jump function.
        int LOG = Math.max(1, 32 - Integer.numberOfLeadingZeros(Math.max(1, n)));
        int[][] up = new int[LOG][n];
        up[0] = R;
        for (int k = 1; k < LOG; k++) {
            for (int i = 0; i < n; i++) {
                up[k][i] = up[k - 1][up[k - 1][i]];
            }
        }

        int[] ans = new int[queries.length];
        for (int q = 0; q < queries.length; q++) {
            int su = rank[queries[q][0]], sv = rank[queries[q][1]];
            if (su > sv) {
                int t = su;
                su = sv;
                sv = t;
            }
            if (su == sv) {
                ans[q] = 0;
            } else if (comp[su] != comp[sv]) {
                ans[q] = -1;
            } else {
                int cur = su, steps = 0;
                for (int k = LOG - 1; k >= 0; k--) {
                    if (up[k][cur] < sv) {
                        cur = up[k][cur];
                        steps += 1 << k;
                    }
                }
                ans[q] = steps + 1; // one final jump reaches sv
            }
        }
        return ans;
    }
}