Watch 5 video solutions for Process Restricted Friend Requests, a hard level problem involving Union Find, Graph. This walkthrough by Tejpratap Pandey has 779 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |