Process Restricted Friend Requests solution and explanation
Google
4 more videos on this problem
2076. Process Restricted Friend Requests | Leetcode Weekly Contest 267 | Graphs | DSU | DFS | DSATejpratap Pandey · 20:58 · 827 views
2076. Process Restricted Friend Requests (Leetcode Hard)Programming Live with Larry · 16:48 · 757 views
【每日一题】LeetCode 2076. Process Restricted Friend RequestsHuifeng Guan · 16:55 · 602 views
Leetcode 2076 || Process Restricted Friend RequestsCode with Akratii · 20:08 · 154 views
LeetCode 2076: Process Restricted Friend RequestsAlitaCode · 33:35 · 8 views
The problem
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.
Example 1:
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 <= 10000 <= restrictions.length <= 1000restrictions[i].length == 20 <= xi, yi <= n - 1xi != yi1 <= requests.length <= 1000requests[j].length == 20 <= uj, vj <= n - 1uj != vj
Approach overview
Problem Overview: You have n users, a list of friendship restrictions, and a sequence of friend requests. Each request asks whether two users can become friends. A request is valid only if accepting it does not indirectly connect any pair of users that are restricted from being in the same friend group.
Approach 1: Graph Check per Request (Brute Force) (Time: O(r * (n + e)), Space: O(n + e))
Model the accepted friendships as an undirected graph. For every request (u, v), temporarily assume the edge exists and check whether any restricted pair becomes connected. You can run a DFS or BFS to verify if the endpoints of a restricted pair fall into the same connected component. If a violation appears, reject the request; otherwise permanently add the edge. This approach is straightforward but inefficient because each request may trigger a full graph traversal.
Approach 2: Union-Find with Path Compression (Time: O(r * m * α(n)), Space: O(n))
Use a Disjoint Set Union structure to maintain connected components of friends. When a request (u, v) arrives, first find their current roots using path compression. If both users already share the same root, the request is automatically valid. Otherwise, scan the restriction list and check whether merging the two components would cause a restricted pair to end up in the same set. This happens if one restricted user belongs to the root of u and the other belongs to the root of v. If no conflict exists, union the two sets. DSU makes component lookups nearly constant with the inverse Ackermann factor α(n).
The key insight is that restrictions apply to entire components, not individual nodes once friendships accumulate. Tracking components with Union-Find avoids repeated graph traversals and keeps connectivity updates efficient. The restriction validation step simply compares roots instead of exploring edges.
Recommended for interviews: Union-Find with path compression. The brute-force graph approach demonstrates understanding of connectivity constraints, but the DSU solution shows strong knowledge of dynamic connectivity problems in graph systems. Interviewers typically expect the Union-Find design because it scales well with many requests.
Approach 1: Approach using Union-Find with Path Compression
The problem can be solved using the Union-Find data structure, also known as Disjoint Set Union (DSU). We use path compression to optimize the find operation. The goal is to manage dynamic connectivity among people, ensuring that no restricted indirect connections are formed.
Each person starts as their own component. To process a friendship request, we first check if making the friends would violate any existing restriction by checking their connected components. If it's safe (meaning they are not indirectly restricted), we use union to merge the two components.
def find(parent, i):
if parent[i] != i:
parent[i] = find(parent, parent[i])
return parent[i]
def union(parent, rank, x, y):
rootX = find(parent, x)
rootY = find(parent, y)
if rootX != rootY:
if rank[rootX] > rank[rootY]:
parent[rootY] = rootX
elif rank[rootX] < rank[rootY]:
parent[rootX] = rootY
else:
parent[rootY] = rootX
rank[rootX] += 1
def processFriendRequests(n, restrictions, requests):
parent = list(range(n))
rank = [0] * n
result = []
def canBeFriends(u, v):
rootU = find(parent, u)
rootV = find(parent, v)
for x, y in restrictions:
if (rootU == find(parent, x) and rootV == find(parent, y)) or (rootV == find(parent, x) and rootU == find(parent, y)):
return False
return True
for u, v in requests:
if canBeFriends(u, v):
union(parent, rank, u, v)
result.append(True)
else:
result.append(False)
return resultclass Solution {
private int find(int[] parent, int i) {
if (parent[i] != i) {
parent[i] = find(parent, parent[i]);
}
return parent[i];
}
private void union(int[] parent, int[] rank, int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public boolean[] processFriendRequests(int n, int[][] restrictions, int[][] requests) {
int[] parent = new int[n];
int[] rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
boolean[] result = new boolean[requests.length];
for (int k = 0; k < requests.length; k++) {
int u = requests[k][0];
int v = requests[k][1];
int rootU = find(parent, u);
int rootV = find(parent, v);
boolean canBeFriends = true;
for (int[] restr : restrictions) {
int xRoot = find(parent, restr[0]);
int yRoot = find(parent, restr[1]);
if ((rootU == xRoot && rootV == yRoot) || (rootU == yRoot && rootV == xRoot)) {
canBeFriends = false;
break;
}
}
if (canBeFriends) {
union(parent, rank, u, v);
result[k] = true;
} else {
result[k] = false;
}
}
return result;
}
}#include <stdbool.h>
int find(int parent[], int i) {
if (parent[i] != i)
parent[i] = find(parent, parent[i]);
return parent[i];
}
void unionSets(int parent[], int rank[], int x, int y) {
int rootX = find(parent, x);
int rootY = find(parent, y);
if (rootX != rootY) {
if (rank[rootX] > rank[rootY])
parent[rootY] = rootX;
else if (rank[rootX] < rank[rootY])
parent[rootX] = rootY;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
bool canBeFriends(int parent[], int n, int restr[][2], int rSize, int u, int v) {
int rootU = find(parent, u);
int rootV = find(parent, v);
for (int i = 0; i < rSize; i++) {
int xRoot = find(parent, restr[i][0]);
int yRoot = find(parent, restr[i][1]);
if ((rootU == xRoot && rootV == yRoot) || (rootU == yRoot && rootV == xRoot))
return false;
}
return true;
}
bool* processFriendRequests(int n, int restrictions[][2], int rSize, int requests[][2], int qSize, int *resultSize) {
*resultSize = qSize;
bool *result = (bool*)malloc(qSize * sizeof(bool));
int parent[n], rank[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
for (int i = 0; i < qSize; i++) {
int u = requests[i][0];
int v = requests[i][1];
if (canBeFriends(parent, n, restrictions, rSize, u, v)) {
unionSets(parent, rank, u, v);
result[i] = true;
} else {
result[i] = false;
}
}
return result;
}The Python code follows the Union-Find pattern with path compression and union by rank. We define helper functions find and union and implement a check for whether a friendship violates any restriction. Successful friend requests update the union structure.
Time Complexity: O((n + m) * α(n)) where α(n) is the inverse Ackermann function.
Space Complexity: O(n) due to the parent and rank lists.
Approach 2: Union-Find
We can use a union-find set to maintain the friend relationships, and then for each request, we determine whether it meets the restriction conditions.
For the two people (u, v) in the current request, if they are already friends, then the request can be directly accepted; otherwise, we traverse the restriction conditions. If there exists a restriction condition (x, y) such that u and x are friends and v and y are friends, or u and y are friends and v and x are friends, then the request cannot be accepted.
The time complexity is O(q times m times log(n)), and the space complexity is O(n). Where q and m are the number of requests and the number of restriction conditions respectively.
class Solution {
public:
vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
vector<int> p(n);
iota(p.begin(), p.end(), 0);
function<int(int)> find = [&](int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
};
vector<bool> ans;
for (auto& req : requests) {
int u = req[0], v = req[1];
int pu = find(u), pv = find(v);
if (pu == pv) {
ans.push_back(true);
} else {
bool ok = true;
for (auto& r : restrictions) {
int px = find(r[0]), py = find(r[1]);
if ((pu == px && pv == py) || (pu == py && pv == px)) {
ok = false;
break;
}
}
ans.push_back(ok);
if (ok) {
p[pu] = pv;
}
}
}
return ans;
}
};function friendRequests(n: number, restrictions: number[][], requests: number[][]): boolean[] {
const p: number[] = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
if (p[x] !== x) {
p[x] = find(p[x]);
}
return p[x];
};
const ans: boolean[] = [];
for (const [u, v] of requests) {
const pu = find(u);
const pv = find(v);
if (pu === pv) {
ans.push(true);
} else {
let ok = true;
for (const [x, y] of restrictions) {
const px = find(x);
const py = find(y);
if ((px === pu && py === pv) || (px === pv && py === pu)) {
ok = false;
break;
}
}
ans.push(ok);
if (ok) {
p[pu] = pv;
}
}
}
return ans;
}func friendRequests(n int, restrictions [][]int, requests [][]int) (ans []bool) {
p := make([]int, n)
for i := range p {
p[i] = i
}
var find func(int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, req := range requests {
pu, pv := find(req[0]), find(req[1])
if pu == pv {
ans = append(ans, true)
} else {
ok := true
for _, r := range restrictions {
px, py := find(r[0]), find(r[1])
if px == pu && py == pv || px == pv && py == pu {
ok = false
break
}
}
ans = append(ans, ok)
if ok {
p[pv] = pu
}
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach using Union-Find with Path Compression | Time Complexity: O((n + m) * α(n)) where α(n) is the inverse Ackermann function. |
| Union-Find | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Graph traversal check per request | O(r * (n + e)) | O(n + e) | Useful for understanding the constraint logic or when request count is very small |
| Union-Find with path compression | O(r * m * α(n)) | O(n) | Best general solution for large inputs with many friend requests |
Frequently asked questions
Is Process Restricted Friend Requests easy or hard?
Process Restricted Friend Requests is classified as Hard because it combines Union-Find with constraint validation across components. The challenge lies in recognizing that restrictions apply to entire connected groups rather than individual users.
Process Restricted Friend Requests Python/Java solution
The typical implementation uses a Union-Find class with parent arrays and path compression. For each request, compute the roots of both users and verify restrictions before performing a union. The same logic works across Python, Java, and C implementations.
How to solve Process Restricted Friend Requests in O(n)?
Use a Union-Find data structure to track connected components. For each request, find the roots of both users and verify that merging them will not place any restricted pair in the same component. If no restriction is violated, union the two sets and accept the request.
What is the best approach for Process Restricted Friend Requests?
Union-Find (Disjoint Set Union) with path compression is the most efficient approach. It keeps track of connected friend groups and checks whether merging two groups would violate any restriction. Each request performs near-constant time root lookups and scans the restriction list to detect conflicts.
Is Process Restricted Friend Requests asked at Google/Amazon/Meta?
Problems involving Union-Find and dynamic connectivity frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests understanding of disjoint sets, graph connectivity, and constraint validation during incremental updates.
What data structure is used in Process Restricted Friend Requests?
The core data structure is Disjoint Set Union (Union-Find). It efficiently tracks which users belong to the same friend group and supports fast union and find operations using path compression.
What is the time complexity of Process Restricted Friend Requests?
The optimized Union-Find solution runs in O(r * m * α(n)) time where r is the number of requests, m is the number of restrictions, and α(n) is the inverse Ackermann function from path compression. Space complexity is O(n) for the parent array storing the disjoint sets.