3534. Path Existence Queries in a Graph II

import java.util.*;

class Solution {
    public int[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {

        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = nums[i];
            pairs[i][1] = i;
        }

        Arrays.sort(pairs, (a, b) -> Integer.compare(a[0], b[0]));

        int LOG = 20;
        int[][] jump = new int[n][LOG];

        int r = n - 1;
        for (int l = n - 1; l >= 0; l--) {

            while (pairs[r][0] - pairs[l][0] > maxDiff) {
                r--;
            }

            int from = pairs[l][1];
            int to = pairs[r][1];

            jump[from][0] = to;

            for (int k = 1; k < LOG; k++) {
                jump[from][k] = jump[jump[from][k - 1]][k - 1];
            }
        }

        int[] ans = new int[queries.length];

        for (int t = 0; t < queries.length; t++) {

            int u = queries[t][0];
            int v = queries[t][1];

            if (nums[u] > nums[v]) {
                int temp = u;
                u = v;
                v = temp;
            }

            if (u == v) {
                ans[t] = 0;
                continue;
            }

            if (nums[u] == nums[v]) {
                ans[t] = 1;
                continue;
            }

            int dist = 0;

            for (int k = LOG - 1; k >= 0; k--) {
                if (nums[jump[u][k]] < nums[v]) {
                    dist += 1 << k;
                    u = jump[u][k];
                }
            }

            if (nums[jump[u][0]] < nums[v]) {
                ans[t] = -1;
            } else {
                ans[t] = dist + 1;
            }
        }

        return ans;
    }
}

class Solution:
    def pathExistenceQueries(self, n, nums, maxDiff, queries):

        pairs = sorted((nums[i], i) for i in range(n))

        LOG = 20
        jump = [[0] * LOG for _ in range(n)]

        r = n - 1
        for l in range(n - 1, -1, -1):

            while pairs[r][0] - pairs[l][0] > maxDiff:
                r -= 1

            frm = pairs[l][1]
            to = pairs[r][1]

            jump[frm][0] = to

            for k in range(1, LOG):
                jump[frm][k] = jump[jump[frm][k - 1]][k - 1]

        ans = []

        for u, v in queries:

            if nums[u] > nums[v]:
                u, v = v, u

            if u == v:
                ans.append(0)
                continue

            if nums[u] == nums[v]:
                ans.append(1)
                continue

            dist = 0

            for k in range(LOG - 1, -1, -1):
                if nums[jump[u][k]] < nums[v]:
                    dist += 1 << k
                    u = jump[u][k]

            if nums[jump[u][0]] < nums[v]:
                ans.append(-1)
            else:
                ans.append(dist + 1)

        return ans

class Solution {
public:
    vector<int> pathExistenceQueries(int n, vector<int>& nums, int maxDiff, vector<vector<int>>& queries) {

        vector<pair<int,int>> pairs;

        for (int i = 0; i < n; i++) {
            pairs.push_back({nums[i], i});
        }

        sort(pairs.begin(), pairs.end());

        const int LOG = 20;
        vector<vector<int>> jump(n, vector<int>(LOG));

        int r = n - 1;

        for (int l = n - 1; l >= 0; l--) {

            while (pairs[r].first - pairs[l].first > maxDiff) {
                r--;
            }

            int from = pairs[l].second;
            int to = pairs[r].second;

            jump[from][0] = to;

            for (int k = 1; k < LOG; k++) {
                jump[from][k] = jump[jump[from][k - 1]][k - 1];
            }
        }

        vector<int> ans;

        for (auto &q : queries) {

            int u = q[0];
            int v = q[1];

            if (nums[u] > nums[v]) swap(u, v);

            if (u == v) {
                ans.push_back(0);
                continue;
            }

            if (nums[u] == nums[v]) {
                ans.push_back(1);
                continue;
            }

            int dist = 0;

            for (int k = LOG - 1; k >= 0; k--) {
                if (nums[jump[u][k]] < nums[v]) {
                    dist += 1 << k;
                    u = jump[u][k];
                }
            }

            if (nums[jump[u][0]] < nums[v]) {
                ans.push_back(-1);
            } else {
                ans.push_back(dist + 1);
            }
        }

        return ans;
    }
};

var pathExistenceQueries = function(n, nums, maxDiff, queries) {

    const pairs = [];

    for (let i = 0; i < n; i++) {
        pairs.push([nums[i], i]);
    }

    pairs.sort((a, b) => a[0] - b[0]);

    const LOG = 20;
    const jump = Array.from({ length: n }, () => Array(LOG).fill(0));

    let r = n - 1;

    for (let l = n - 1; l >= 0; l--) {

        while (pairs[r][0] - pairs[l][0] > maxDiff) {
            r--;
        }

        const from = pairs[l][1];
        const to = pairs[r][1];

        jump[from][0] = to;

        for (let k = 1; k < LOG; k++) {
            jump[from][k] = jump[jump[from][k - 1]][k - 1];
        }
    }

    const ans = [];

    for (let [u, v] of queries) {

        if (nums[u] > nums[v]) {
            [u, v] = [v, u];
        }

        if (u === v) {
            ans.push(0);
            continue;
        }

        if (nums[u] === nums[v]) {
            ans.push(1);
            continue;
        }

        let dist = 0;

        for (let k = LOG - 1; k >= 0; k--) {
            if (nums[jump[u][k]] < nums[v]) {
                dist += 1 << k;
                u = jump[u][k];
            }
        }

        if (nums[jump[u][0]] < nums[v]) {
            ans.push(-1);
        } else {
            ans.push(dist + 1);
        }
    }

    return ans;
};