2076. Process Restricted Friend Requests LeetCode Solution
In this guide, you will get 2076. Process Restricted Friend Requests LeetCode Solution with the best time and space complexity. The solution to Process Restricted Friend Requests 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 Process Restricted Friend Requests
You are given an integer n indicating the number of people in a network. Each person is labeled from 0 to n – 1.
You are also given a 0-indexed 2D integer array restrictions, where restrictions[i] = [xi, yi] means that person xi and person yi cannot become friends, either directly or indirectly through other people.
Initially, no one is friends with each other. You are given a list of friend requests as a 0-indexed 2D integer array requests, where requests[j] = [uj, vj] is a friend request between person uj and person vj.
A friend request is successful if uj and vj can be friends. Each friend request is processed in the given order (i.e., requests[j] occurs before requests[j + 1]), and upon a successful request, uj and vj become direct friends for all future friend requests.
Return a boolean array result, where each result[j] is true if the jth friend request is successful or false if it is not.
Note: If uj and vj are already direct friends, the request is still successful.
Input: n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]
Output: [true,false]
Explanation:
Request 0: Person 0 and person 2 can be friends, so they become direct friends.
Request 1: Person 2 and person 1 cannot be friends since person 0 and person 1 would be indirect friends (1–2–0).
Example 2:
Input: n = 3, restrictions = [[0,1]], requests = [[1,2],[0,2]]
Output: [true,false]
Explanation:
Request 0: Person 1 and person 2 can be friends, so they become direct friends.
Request 1: Person 0 and person 2 cannot be friends since person 0 and person 1 would be indirect friends (0–2–1).
Example 3:
Input: n = 5, restrictions = [[0,1],[1,2],[2,3]], requests = [[0,4],[1,2],[3,1],[3,4]]
Output: [true,false,true,false]
Explanation:
Request 0: Person 0 and person 4 can be friends, so they become direct friends.
Request 1: Person 1 and person 2 cannot be friends since they are directly restricted.
Request 2: Person 3 and person 1 can be friends, so they become direct friends.
Request 3: Person 3 and person 4 cannot be friends since person 0 and person 1 would be indirect friends (0–4–3–1).
Constraints:
2 <= n <= 1000
0 <= restrictions.length <= 1000
restrictions[i].length == 2
0 <= xi, yi <= n – 1
xi != yi
1 <= requests.length <= 1000
requests[j].length == 2
0 <= uj, vj <= n – 1
uj != vj
Complexity Analysis
Time Complexity: O(|\texttt{restrictions}||\texttt{requests}|\cdot\log n)
Space Complexity: O(n)
2076. Process Restricted Friend Requests 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> friendRequests(int n, vector<vector<int>>& restrictions,
vector<vector<int>>& requests) {
vector<bool> ans;
UnionFind uf(n);
for (const vector<int>& request : requests) {
const int i = uf.find(request[0]);
const int j = uf.find(request[1]);
bool isValid = true;
if (i != j)
for (const vector<int>& restriction : restrictions) {
const int x = uf.find(restriction[0]);
const int y = uf.find(restriction[1]);
if (i == x && j == y || i == y && j == x) {
isValid = false;
break;
}
}
ans.push_back(isValid);
if (isValid)
uf.unionByRank(i, j);
}
return ans;
}
}; /* code provided by PROGIEZ */
2076. Process Restricted Friend Requests 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[] friendRequests(int n, int[][] restrictions, int[][] requests) {
boolean[] ans = new boolean[requests.length];
UnionFind uf = new UnionFind(n);
for (int i = 0; i < requests.length; ++i) {
final int pu = uf.find(requests[i][0]);
final int pv = uf.find(requests[i][1]);
boolean isValid = true;
if (pu != pv)
for (int[] restriction : restrictions) {
final int px = uf.find(restriction[0]);
final int py = uf.find(restriction[1]);
if (pu == px && pv == py || pu == py && pv == px) {
isValid = false;
break;
}
}
ans[i] = isValid;
if (isValid)
uf.unionByRank(pu, pv);
}
return ans;
}
} // code provided by PROGIEZ
2076. Process Restricted Friend Requests 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 friendRequests(
self,
n: int,
restrictions: list[list[int]],
requests: list[list[int]],
) -> list[bool]:
ans = []
uf = UnionFind(n)
for u, v in requests:
pu = uf.find(u)
pv = uf.find(v)
isValid = True
if pu != pv:
for x, y in restrictions:
px = uf.find(x)
py = uf.find(y)
if (pu, pv) in [(px, py), (py, px)]:
isValid = False
break
ans.append(isValid)
if isValid:
uf.unionByRank(pu, pv)
return ans # code by PROGIEZ
