Daily LeetCode - by Vítor Belim

Description

You are given an integer n representing the number of nodes in a graph, labeled from 0 to n - 1.

You are also given an integer array nums of length n and an integer maxDiff.

An undirected edge exists between nodes i and j if the absolute difference between nums[i] and nums[j] is at most maxDiff (i.e., |nums[i] - nums[j]| <= maxDiff).

You are also given a 2D integer array queries. For each queries[i] = [u_i, v_i], find the minimum distance between nodes u_i and v_i_. If no path exists between the two nodes, return -1 for that query.

Return an array answer, where answer[i] is the result of the i^th query.

Note: The edges between the nodes are unweighted.

Example 1:

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

Output: [1,1]

Explanation:

The resulting graph is:

Query	Shortest Path	Minimum Distance
[0, 3]	0 → 3	1
[2, 4]	2 → 4	1

Thus, the output is [1, 1].

Example 2:

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

Output: [1,2,-1,1]

Explanation:

The resulting graph is:

Query	Shortest Path	Minimum Distance
[0, 1]	0 → 1	1
[0, 2]	0 → 1 → 2	2
[2, 3]	None	-1
[4, 3]	3 → 4	1

Thus, the output is [1, 2, -1, 1].

Example 3:

Input: n = 3, nums = [3,6,1], maxDiff = 1, queries = [[0,0],[0,1],[1,2]]

Output: [0,-1,-1]

Explanation:

There are no edges between any two nodes because:

Nodes 0 and 1: |nums[0] - nums[1]| = |3 - 6| = 3 > 1
Nodes 0 and 2: |nums[0] - nums[2]| = |3 - 1| = 2 > 1
Nodes 1 and 2: |nums[1] - nums[2]| = |6 - 1| = 5 > 1

Thus, no node can reach any other node, and the output is [0, -1, -1].

Constraints:

1 <= n == nums.length <= 10⁵
0 <= nums[i] <= 10⁵
0 <= maxDiff <= 10⁵
1 <= queries.length <= 10⁵
queries[i] == [u_i, v_i]
0 <= u_i, v_i < n

Solutions

Used Claude (free account) to figure out how my solution could be improved. Binary lifting (whatever that is) was the answer, and the results were seriously impressive: 100 / 100.

Language: javascript(2026-07-10 11:40)DONE

CPU Performance100.00%

Memory Performance100.00%

/**
 * @param {number} n
 * @param {number[]} nums
 * @param {number} maxDiff
 * @param {number[][]} queries
 * @return {number[]}
 */
var pathExistenceQueries = function(n, nums, maxDiff, queries) {
    // Rank space: work with indices sorted by value.
    const order = Array.from({ length: n }, (_, i) => i).sort((a, b) => nums[a] - nums[b]);
    const sortedNums = new Array(n);
    const pos = new Int32Array(n); // pos[originalIndex] = rank
    for (let k = 0; k < n; k++) {
        sortedNums[k] = nums[order[k]];
        pos[order[k]] = k;
    }

    // Connected-component id per rank — O(n)
    const group = new Int32Array(n);
    for (let k = 1; k < n; k++) {
        group[k] = group[k - 1] + (sortedNums[k] - sortedNums[k - 1] > maxDiff ? 1 : 0);
    }

    // next[k] = farthest rank reachable in ONE greedy hop from k — O(n), two pointers
    const next0 = new Int32Array(n);
    let far = 0;
    for (let k = 0; k < n; k++) {
        if (far < k) far = k;
        while (far + 1 < n && sortedNums[far + 1] - sortedNums[k] <= maxDiff) far++;
        next0[k] = far;
    }

    // Binary lifting table: up[j][k] = rank reached after 2^j greedy hops from k
    const LOG = Math.max(1, Math.ceil(Math.log2(n + 1)));
    const up = [next0];
    for (let j = 1; j < LOG; j++) {
        const prev = up[j - 1];
        const cur = new Int32Array(n);
        for (let k = 0; k < n; k++) cur[k] = prev[prev[k]];
        up.push(cur);
    }

    // Min hops from rank lo to reach rank >= hi (same component, lo <= hi)
    const minHops = (lo, hi) => {
        if (lo === hi) return 0;

        let cur = lo;
        let hops = 0;

        for (let j = LOG - 1; j >= 0; j--) {
            if (up[j][cur] < hi) {
                hops += 1 << j;
                cur = up[j][cur];
            }
        }

        return hops + 1;
    };

    const res = new Array(queries.length);

    for (let q = 0; q < queries.length; q++) {
        const pu = pos[queries[q][0]];
        const pv = pos[queries[q][1]];

        if (group[pu] !== group[pv]) {
            res[q] = -1;
            continue;
        }

        const lo = Math.min(pu, pv);
        const hi = Math.max(pu, pv);
        res[q] = minHops(lo, hi);
    }

    return res;
};

Description

Solutions

Developer Notes

AI Explanation