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 != vjProblem 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.
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.
The C implementation defines find and unionSets functions to manage connected components. In processFriendRequests(), we iterate over each request and check if the associated friendship is safe by comparing their root components with the restricted pairs. If safe, we merge the friend groups, else decline the request.
Time Complexity: O((n + m) * α(n)) where α(n) is the inverse Ackermann function, very small and close to constant for practical inputs.
Space Complexity: O(n) for storing parent and rank arrays.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach using Union-Find with Path Compression | Time Complexity: O((n + m) * α(n)) where α(n) is the inverse Ackermann function, very small and close to constant for practical inputs. |
| Union-Find | — |
| 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 |
2076. Process Restricted Friend Requests | Leetcode Weekly Contest 267 | Graphs | DSU | DFS | DSA • Tejpratap Pandey • 779 views views
Watch 4 more video solutions →Practice Process Restricted Friend Requests with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor