In this guide, you will get 3534. Path Existence Queries in a Graph II LeetCode Solution with the best time and space complexity. The solution to Path Existence Queries in a Graph II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Path Existence Queries in a Graph II
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] = [ui, vi], find the minimum distance between nodes ui and vi. 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 ith 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:
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:
3534. Path Existence Queries in a Graph II LeetCode Solution in C++
class Solution {
public:
vector<int> pathExistenceQueries(int n, vector<int>& nums, int maxDiff,
vector<vector<int>>& queries) {
vector<int> ans;
vector<int> sortedNums;
vector<int> indexMap(n);
vector<pair<int, int>> sortedNumAndIndexes;
for (int i = 0; i < n; ++i)
sortedNumAndIndexes.emplace_back(nums[i], i);
ranges::sort(sortedNumAndIndexes);
for (int i = 0; i < n; ++i) {
const auto& [num, sortedIndex] = sortedNumAndIndexes[i];
sortedNums.push_back(num);
indexMap[sortedIndex] = i;
}
const int maxLevel = std::bit_width(static_cast<unsigned>(n)) + 1;
// jump[i][j] := the index of the j-th ancestor of i
vector<vector<int>> jump(n, vector<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) {
const int prevJump = jump[i][level - 1];
jump[i][level] = jump[prevJump][level - 1];
}
for (const vector<int>& query : queries) {
const int u = query[0];
const int v = query[1];
const int uIndex = indexMap[u];
const int vIndex = indexMap[v];
const int start = min(uIndex, vIndex);
const int end = max(uIndex, vIndex);
const int res = minJumps(jump, start, end, maxLevel - 1);
ans.push_back(res == INT_MAX ? -1 : res);
}
return ans;
}
private:
// Returns the minimum number of jumps from `start` to `end` using binary
// lifting.
int minJumps(const vector<vector<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_MAX;
int j = level;
for (; j >= 0; --j)
if (jump[start][j] < end)
break;
return (1 << j) + minJumps(jump, jump[start][j], end, j);
}
}; /* code provided by PROGIEZ */
3534. Path Existence Queries in a Graph II LeetCode Solution in Java
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];
Pair<Integer, Integer>[] sortedNumAndIndexes = new Pair[n];
for (int i = 0; i < n; ++i)
sortedNumAndIndexes[i] = new Pair<>(nums[i], i);
Arrays.sort(sortedNumAndIndexes, Comparator.comparingInt(Pair::getKey));
for (int i = 0; i < n; ++i) {
final int num = sortedNumAndIndexes[i].getKey();
final int sortedIndex = sortedNumAndIndexes[i].getValue();
sortedNums[i] = num;
indexMap[sortedIndex] = i;
}
final int maxLevel = Integer.SIZE - Integer.numberOfLeadingZeros(n) + 1;
// jump[i][j] := the index of the j-th ancestor of i
int[][] jump = new int[n][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) {
final int prevJump = jump[i][level - 1];
jump[i][level] = jump[prevJump][level - 1];
}
for (int i = 0; i < queries.length; ++i) {
final int u = queries[i][0];
final int v = queries[i][1];
final int uIndex = indexMap[u];
final int vIndex = indexMap[v];
final int start = Math.min(uIndex, vIndex);
final int end = Math.max(uIndex, vIndex);
final int res = minJumps(jump, start, end, maxLevel - 1);
ans[i] = res == Integer.MAX_VALUE ? -1 : res;
}
return ans;
}
// Returns the minimum number of jumps from `start` to `end` using binary
// lifting.
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 Integer.MAX_VALUE;
int j = level;
for (; j >= 0; --j)
if (jump[start][j] < end)
break;
return (1 << j) + minJumps(jump, jump[start][j], end, j);
}
} // code provided by PROGIEZ
3534. Path Existence Queries in a Graph II LeetCode Solution in Python
class Solution:
def pathExistenceQueries(
self,
n: int,
nums: list[int],
maxDiff: int,
queries: list[list[int]],
) -> list[int]:
sortedNumAndIndexes = sorted((num, i) for i, num in enumerate(nums))
sortedNums = [num for num, _ in sortedNumAndIndexes]
indexMap = {originalIndex: sortedIndex for sortedIndex,
(_, originalIndex) in enumerate(sortedNumAndIndexes)}
maxLevel = n.bit_length() + 1
# jump[i][j] is the index of the j-th ancestor of i
jump = [[0] * maxLevel for _ in range(n)]
right = 0
for i in range(n):
while right + 1 < n and sortedNums[right + 1] - sortedNums[i] <= maxDiff:
right += 1
jump[i][0] = right
for level in range(1, maxLevel):
for i in range(n):
prevJump = jump[i][level - 1]
jump[i][level] = jump[prevJump][level - 1]
def minJumps(start: int, end: int, level: int) -> int:
"""
Returns the minimum number of jumps from `start` to `end` using binary
lifting.
"""
if start == end:
return 0
if jump[start][0] >= end:
return 1
if jump[start][level] < end:
return math.inf
for j in range(level, -1, -1):
if jump[start][j] < end:
break
return (1 << j) + minJumps(jump[start][j], end, j)
def minDist(u: int, v: int) -> int:
uIndex = indexMap[u]
vIndex = indexMap[v]
start = min(uIndex, vIndex)
end = max(uIndex, vIndex)
res = minJumps(start, end, maxLevel - 1)
return res if res < math.inf else -1
return [minDist(u, v) for u, v in queries] # code by PROGIEZ
