3532. Path Existence Queries in a Graph I LeetCode Solution
In this guide, you will get 3532. Path Existence Queries in a Graph I LeetCode Solution with the best time and space complexity. The solution to Path Existence Queries in a Graph I 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.
Table of Contents
- Problem Statement
- Complexity Analysis
- Path Existence Queries in a Graph I solution in C++
- Path Existence Queries in a Graph I solution in Java
- Path Existence Queries in a Graph I solution in Python
- Additional Resources
Problem Statement of Path Existence Queries in a Graph I
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 sorted in non-decreasing order, 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], determine whether there exists a path between nodes ui and vi.
Return a boolean array answer, where answer[i] is true if there exists a path between ui and vi in the ith query and false otherwise.
Example 1:
Input: n = 2, nums = [1,3], maxDiff = 1, queries = [[0,0],[0,1]]
Output: [true,false]
Explanation:
Query [0,0]: Node 0 has a trivial path to itself.
Query [0,1]: There is no edge between Node 0 and Node 1 because |nums[0] – nums[1]| = |1 – 3| = 2, which is greater than maxDiff.
Thus, the final answer after processing all the queries is [true, false].
Example 2:
Input: n = 4, nums = [2,5,6,8], maxDiff = 2, queries = [[0,1],[0,2],[1,3],[2,3]]
Output: [false,false,true,true]
Explanation:
The resulting graph is:
Query [0,1]: There is no edge between Node 0 and Node 1 because |nums[0] – nums[1]| = |2 – 5| = 3, which is greater than maxDiff.
Query [0,2]: There is no edge between Node 0 and Node 2 because |nums[0] – nums[2]| = |2 – 6| = 4, which is greater than maxDiff.
Query [1,3]: There is a path between Node 1 and Node 3 through Node 2 since |nums[1] – nums[2]| = |5 – 6| = 1 and |nums[2] – nums[3]| = |6 – 8| = 2, both of which are within maxDiff.
Query [2,3]: There is an edge between Node 2 and Node 3 because |nums[2] – nums[3]| = |6 – 8| = 2, which is equal to maxDiff.
Thus, the final answer after processing all the queries is [false, false, true, true].
Constraints:
1 <= n == nums.length <= 105
0 <= nums[i] <= 105
nums is sorted in non-decreasing order.
0 <= maxDiff <= 105
1 <= queries.length <= 105
queries[i] == [ui, vi]
0 <= ui, vi < n
Complexity Analysis
- Time Complexity: O(n\log^* n + q)
- Space Complexity: O(n + q)
3532. Path Existence Queries in a Graph I LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), rank(n) {
iota(id.begin(), id.end(), 0);
}
void unionByRank(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
private:
vector<int> id;
vector<int> rank;
};
class Solution {
public:
vector<bool> pathExistenceQueries(int n, vector<int>& nums, int maxDiff,
vector<vector<int>>& queries) {
vector<bool> ans;
UnionFind uf(n);
for (int i = 1; i < n; ++i)
if (abs(nums[i] - nums[i - 1]) <= maxDiff)
uf.unionByRank(i, i - 1);
for (const vector<int>& query : queries) {
const int u = query[0];
const int v = query[1];
ans.push_back(uf.find(u) == uf.find(v));
}
return ans;
}
};
/* code provided by PROGIEZ */3532. Path Existence Queries in a Graph I LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public void unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
private int[] id;
private int[] rank;
}
class Solution {
public boolean[] pathExistenceQueries(int n, int[] nums, int maxDiff, int[][] queries) {
boolean[] ans = new boolean[queries.length];
UnionFind uf = new UnionFind(n);
for (int i = 1; i < n; ++i)
if (Math.abs(nums[i] - nums[i - 1]) <= maxDiff)
uf.unionByRank(i, i - 1);
for (int i = 0; i < queries.length; ++i) {
final int u = queries[i][0];
final int v = queries[i][1];
ans[i] = uf.find(u) == uf.find(v);
}
return ans;
}
}
// code provided by PROGIEZ3532. Path Existence Queries in a Graph I LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
def unionByRank(self, u: int, v: int) -> None:
i = self.find(u)
j = self.find(v)
if i == j:
return
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
class Solution:
def pathExistenceQueries(
self,
n: int,
nums: list[int],
maxDiff: int,
queries: list[list[int]]
) -> list[bool]:
uf = UnionFind(n)
for i in range(1, n):
if abs(nums[i] - nums[i - 1]) <= maxDiff:
uf.unionByRank(i, i - 1)
return [uf.find(u) == uf.find(v)
for u, v in queries]
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.