3534. Path Existence Queries in a Graph II

Array Sorting Binary Search Graph Greedy

Problem Overview

Unlike LC 3532, nums is not sorted by index and each query asks for the shortest path length (edge count), not just connectivity.

Intuition

Unlike LC 3532, nums is not sorted by index and each query asks for the shortest path length (edge count), not just connectivity. Sort nodes by value: an edge can only connect values within maxDiff, so from any sorted position the farthest one-hop landing is a contiguous right endpoint. Precompute that endpoint, then binary-lift to jump 2^k hops and answer each query in O(log n).

Algorithm

1Sort (nums[i], i) pairs; build sortedNums and indexMap[original] → sorted rank.
2Two pointers: for each sorted index i, advance right while sortedNums[right] − sortedNums[i] ≤ maxDiff; set jump[i][0] = right.
3Binary lifting: jump[i][k] = jump[jump[i][k−1]][k−1].
4For query [u,v]: start = min(rank[u], rank[v]), end = max(...).
5If jump[start][maxLevel] < end, return −1 (cannot reach).
6Otherwise greedily take the largest 2^j jump that stays strictly before end, recurse, add 1 << j (or return 1 if one hop reaches end).

Example Walkthrough

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

1.Sorted values: 1,2,3,5,8 with ranks for original indices.
2.From value 1, one hop can reach up through 2,3 (diff ≤ 3) but not necessarily all the way to 8.
3.Binary lifting finds the minimum number of such maxDiff-hops between the two ranks.
4.If a gap larger than maxDiff separates components, answer is −1.

Output: minimum edge counts (or -1) per query

Common Pitfalls

•Must sort by value first — unlike 3532, index order is not sorted.
•Distance is number of edges (jumps), not |u−v| in index space.
•If jump[start][0] already ≥ end, answer is 1; if start == end, answer is 0.
•Return −1 when even the farthest binary-lifted position never reaches end.

3534.cs

// Approach: Sort nodes by nums value. From each sorted position, the farthest reachable
// index in one edge is the rightmost j with sortedNums[j] - sortedNums[i] <= maxDiff.
// Binary-lift those jumps; each query is the min jump count between the two ranks (or -1).
// Time: O((n + q) log n) Space: O(n log n)
public class Solution
{
    public int[] PathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries)
    {
        int[] ans = new int[queries.Length];
        int[] indexMap = new int[n];
        int[] sortedNums = new int[n];
        KeyValuePair<int, int>[] sortedNumAndIndexes = new KeyValuePair<int, int>[n];

        for (int i = 0; i < n; ++i)
            sortedNumAndIndexes[i] = new KeyValuePair<int, int>(nums[i], i);

        Array.Sort(sortedNumAndIndexes, (a, b) => a.Key.CompareTo(b.Key));

        for (int i = 0; i < n; ++i)
        {
            int num = sortedNumAndIndexes[i].Key;
            int sortedIndex = sortedNumAndIndexes[i].Value;
            sortedNums[i] = num;
            indexMap[sortedIndex] = i;
        }

        int maxLevel = sizeof(int) * 8 - BitOperations.LeadingZeroCount((uint)n) + 1;
        int[][] jump = new int[n][];
        for (int i = 0; i < n; i++)
            jump[i] = new int[maxLevel];

        int right = 0;
        for (int i = 0; i < n; ++i)
        {
            while (right + 1 < n && sortedNums[right + 1] - sortedNums[i] <= maxDiff)
                ++right;
            jump[i][0] = right;
        }

        for (int level = 1; level < maxLevel; ++level)
        {
            for (int i = 0; i < n; ++i)
            {
                int prevJump = jump[i][level - 1];
                jump[i][level] = jump[prevJump][level - 1];
            }
        }

        for (int i = 0; i < queries.Length; ++i)
        {
            int u = queries[i][0];
            int v = queries[i][1];
            int uIndex = indexMap[u];
            int vIndex = indexMap[v];
            int start = Math.Min(uIndex, vIndex);
            int end = Math.Max(uIndex, vIndex);
            int res = MinJumps(jump, start, end, maxLevel - 1);
            ans[i] = res == int.MaxValue ? -1 : res;
        }

        return ans;
    }

    private int MinJumps(int[][] jump, int start, int end, int level)
    {
        if (start == end)
            return 0;
        if (jump[start][0] >= end)
            return 1;
        if (jump[start][level] < end)
            return int.MaxValue;
        int j = level;
        for (; j >= 0; --j)
            if (jump[start][j] < end)
                break;
        return (1 << j) + MinJumps(jump, jump[start][j], end, j);
    }
}

Was this solution helpful?