2076. Process Restricted Friend Requests
Problem Description
In the given problem, we envision a network of people, initially with no friendships established. Each person in this network is uniquely identified by a label, which is a number starting from 0
to n - 1
. We also have a list of restrictions, where each restriction specifies two people who cannot become friends, either directly or through mutual friends.
On top of these restrictions, we are given a series of friend requests. Each request is a pair of individuals who wish to become friends. Our task is to determine for each friend request whether it could be successful given the constraints of the restrictions.
The result should be an array of boolean values corresponding to each friend request, indicating true
if they can become friends, or false
otherwise. Even if two people are already direct friends, subsequent requests between them should be considered successful.
Intuition
To solve this problem, we need to manage friend connections in such a way that we can quickly check if two people can become friends considering current friendships and restrictions.
The Union-Find algorithm, or Disjoint Set Union (DSU), is well-suited for this kind of problem as it efficiently handles grouping elements into disjoint sets and checking whether two elements belong to the same set.
Initially, each person forms a set of their own. The find
function is used to find the representative of a person's set; if two people have the same representative, they are in the same connected component and hence indirectly friends.
When processing each friend request, we check if they can be added to each other's group. If they are not already in the same group, we examine all the restrictions. If either person in the request matches a pair in the restrictions with the other person in the request, then the friend request is invalid.
If none of the restrictions apply, the request is successful, and we union the two sets representing the requester and the requestee by updating the representative of one of the sets. This way, both individuals will have the same representative and thus be directly connected.
The union
operation is performed by updating the parent of one representative to be the other, effectively merging the sets.
Each friend request's result, whether successful or not, is appended to an ans
list, which is returned at the end of the process.
Learn more about Union Find and Graph patterns.
Solution Approach
The solution implements the Union-Find algorithm, which is a vital part of this approach. Here we will break down how the algorithm is applied within the provided solution code.
-
Parent Array Initialization: A parent array
p
is initialized to contain each element as its own parent, indicating that every individual starts in their own distinct set. This array keeps track of connections.1p = list(range(n))
-
Find Function: The
find()
function is a recursive function that finds and returns the representative (or the "root" parent) of the set that an individual belongs to. It implements path compression by updating the parent of each node to its root parent during the traversal. This optimization decreases the time complexity of subsequentfind()
operations.1def find(x): 2 if p[x] != x: 3 p[x] = find(p[x]) 4 return p[x]
-
Processing Friend Requests: Friend requests are processed in the given order. For each friend request between
u
andv
, we perform the following:-
Check if
u
andv
already have the same representative, meaning they are in the same set (directly or indirectly friends). If so, the request is immediately successful. -
If they are not in the same set, examine all the restrictions. For each restriction pair
(x, y)
, check ifu
orv
is restricted with the other by comparing their representatives withx
andy
. If a restriction is violated, the request cannot be fulfilled, and it is marked as invalid. -
If the request does not violate any restrictions, it is considered successful, and we perform the union operation. This means that we update the parent of one person's representative (
find(u)
) to be the other's representative (find(v)
), effectively merging their sets.
1ans = [] 2for u, v in requests: 3 if find(u) == find(v): 4 ans.append(True) 5 else: 6 valid = True 7 for x, y in restrictions: 8 if (find(u) == find(x) and find(v) == find(y)) or ( 9 find(u) == find(y) and find(v) == find(x) 10 ): 11 valid = False 12 break 13 ans.append(valid) 14 if valid: 15 p[find(u)] = find(v)
-
-
Returning the Result: After iterating through all the requests, the list
ans
is filled with the results of the friend requests (True
for a successful friend request,False
otherwise). The list is returned as the final output.1return ans
By leveraging the Union-Find algorithm with path compression, the solution ensures that we can efficiently determine the outcome of friend requests while respecting the constraints imposed by the restrictions.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us consider an example where we have n = 5
people labeled from 0
to 4
, and we have a list of restrictions restrictions = [(0, 1), (3, 4)]
, which indicates that person 0
cannot be friends with person 1
and person 3
cannot be friends with person 4
. We also have a series of friend requests: requests = [(0, 2), (1, 2), (0, 1), (3, 4), (2, 3)]
.
Let's walk through the friend requests using the solution approach:
-
Parent Array Initialization: Initially, the parent array
p
is[0, 1, 2, 3, 4]
, with each person as their own parent. -
Find Function: This will be used to find the representatives of each person's set as we process the requests.
-
Processing Friend Requests:
-
Request
(0, 2)
: Sincefind(0) == 0
andfind(2) == 2
, they are not in the same set. There are no restrictions involving0
and2
, so they can be friends. We perform the union by settingp[find(0)] = find(2)
, so nowp[0] = 2
. The parent array is now[2, 1, 2, 3, 4]
. -
Request
(1, 2)
: Now,find(1) == 1
andfind(2) == 2
. They are not restricted and are not in the same set, so they can also be friends. After the union,p[1] = 2
. The parent array is[2, 2, 2, 3, 4]
. -
Request
(0, 1)
: Both have the same representative (find(0)
andfind(1)
are both2
), hence they can still become friends. Since they are already in the same set, no changes are made to the parent array. -
Request
(3, 4)
: They're not in the same set (find(3) == 3
andfind(4) == 4
), but they have a direct restriction, so the request is denied. No change is made to the parent array. -
Request
(2, 3)
: No direct restriction involves2
and3
, and since they are not in the same set (find(2) == 2
andfind(3) == 3
), they can be friends. We perform the unionp[find(2)] = find(3)
, and the parent array becomes[2, 2, 3, 3, 4]
.
-
-
Returning the Result: The results for the friend requests are
[True, True, True, False, True]
. This indicates the outcome of each friend request after considering all the restrictions and the current state of friendships.
By using the Union-Find algorithm with optimizations such as path compression, we've efficiently processed the friend requests and determined the successful and unsuccessful connections in this network of people.
Solution Implementation
1from typing import List
2
3class Solution:
4 def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
5 # Initialize the parent array for the union-find data structure
6 parent = list(range(n))
7
8 def find(x):
9 # Path compression: make each checked node point to the root directly
10 if parent[x] != x:
11 parent[x] = find(parent[x])
12 return parent[x]
13
14 # Initialize an empty list to store the answers for each request
15 answers = []
16
17 # Process each friend request
18 for u, v in requests:
19 # Find the roots for both users
20 rootU = find(u)
21 rootV = find(v)
22
23 # If they are already connected, the request is valid
24 if rootU == rootV:
25 answers.append(True)
26 continue
27
28 # Assume the request is valid until we find a restriction that blocks it
29 valid = True
30 for x, y in restrictions:
31 # Check for each restriction whether connecting u and v would violate it
32 if (find(u) == find(x) and find(v) == find(y)) or (find(u) == find(y) and find(v) == find(x)):
33 # If either condition is true, the request is invalid
34 valid = False
35 break
36 # Append the validity of the current request
37 answers.append(valid)
38
39 # If the request is valid, unite the sets of u and v
40 if valid:
41 parent[rootU] = rootV
42
43 # Return the list of results for all requests
44 return answers
45
1class Solution {
2 private int[] parent;
3
4 /**
5 * Determines if requests between friends are valid considering the restrictions.
6 * @param n The total number of people.
7 * @param restrictions Array of pairs representing direct friend restrictions.
8 * @param requests Array of pairs representing friend requests to validate.
9 * @return Boolean array where each element indicates whether the corresponding friend request is valid.
10 */
11 public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
12 parent = new int[n];
13 // Initialize each person to be parent of themselves.
14 for (int i = 0; i < n; ++i) {
15 parent[i] = i;
16 }
17
18 boolean[] results = new boolean[requests.length];
19
20 // Process each friend request.
21 for (int i = 0; i < requests.length; i++) {
22 int personA = requests[i][0];
23 int personB = requests[i][1];
24
25 // If person A and person B already have the same parent, request is valid (they are already friends).
26 if (find(personA) == find(personB)) {
27 results[i] = true;
28 } else {
29 boolean isValid = true; // Flag to check against restrictions.
30
31 // Check each restriction pair against the current friend request.
32 for (int[] restriction : restrictions) {
33 int restrictedPersonA = restriction[0];
34 int restrictedPersonB = restriction[1];
35
36 // If the request conflicts with a restriction, mark as invalid.
37 if ((find(personA) == find(restrictedPersonA) && find(personB) == find(restrictedPersonB))
38 || (find(personA) == find(restrictedPersonB) && find(personB) == find(restrictedPersonA))) {
39 isValid = false;
40 break;
41 }
42 }
43
44 // If valid, union the two sets and set the request as valid.
45 if (isValid) {
46 union(personA, personB);
47 results[i] = true;
48 } else {
49 results[i] = false;
50 }
51 }
52 }
53
54 return results;
55 }
56
57 /**
58 * Finds the root parent of a given person, with path compression.
59 * @param person The person for whom to find the parent.
60 * @return The root parent of the person.
61 */
62 private int find(int person) {
63 if (parent[person] != person) {
64 parent[person] = find(parent[person]);
65 }
66 return parent[person];
67 }
68
69 /**
70 * Unifies two subsets into a single subset.
71 * @param a First person's index.
72 * @param b Second person's index.
73 */
74 private void union(int a, int b) {
75 // Attach one tree's root as a child of the other tree's root.
76 parent[find(a)] = find(b);
77 }
78}
79
1class Solution {
2public:
3 // Using a vector to represent the disjoint set union (DSU) structure
4 vector<int> parent;
5
6 // Function to check if friend requests can be accepted given restrictions
7 vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {
8 // Initialize the disjoint set with each node being its own parent
9 parent.resize(n);
10 for (int i = 0; i < n; ++i) {
11 parent[i] = i;
12 }
13
14 // Vector to store the results of each friend request
15 vector<bool> answer;
16 // Loop over all friend requests
17 for (auto& request : requests) {
18 // Extract the two users involved in the friend request
19 int user1 = request[0], user2 = request[1];
20
21 // Check if the two users are already connected.
22 // If they are, the new friend request is redundant and thus automatically valid.
23 if (findParent(user1) == findParent(user2)) {
24 answer.push_back(true);
25 } else {
26 // Assume the request is valid initially
27 bool isValidRequest = true;
28 // Check all the restrictions to see if the current friend request violates any
29 for (auto& restriction : restrictions) {
30 int restrictedUser1 = restriction[0], restrictedUser2 = restriction[1];
31 // If the friend request connects two users such that it would violate
32 // a restriction, mark as invalid and break out of the loop.
33 if ((findParent(user1) == findParent(restrictedUser1) && findParent(user2) == findParent(restrictedUser2)) ||
34 (findParent(user1) == findParent(restrictedUser2) && findParent(user2) == findParent(restrictedUser1))) {
35 isValidRequest = false;
36 break;
37 }
38 }
39
40 // Add the result of the validity check to the answer vector
41 answer.push_back(isValidRequest);
42
43 // If the request is valid, unite the two sets representing the users
44 if (isValidRequest) {
45 parent[findParent(user1)] = findParent(user2);
46 }
47 }
48 }
49
50 // Return the vector of boolean values representing the validity of each request
51 return answer;
52 }
53
54 // Function to find the root of the set that the element 'x' belongs to
55 int findParent(int x) {
56 // Path compression optimization: make every visited node point to the root directly
57 if (parent[x] != x) {
58 parent[x] = findParent(parent[x]);
59 }
60 return parent[x];
61 }
62};
63
1// Represents the disjoint set union (DSU) structure
2let parent: number[];
3
4// Function to check if friend requests can be accepted given restrictions
5function friendRequests(n: number, restrictions: number[][], requests: number[][]): boolean[] {
6 // Initialize the disjoint set with each element being its own parent
7 parent = Array.from({length: n}, (_, index) => index);
8
9 // Array to store the results of each friend request
10 let answers: boolean[] = [];
11
12 // Iterate over all friend requests
13 for (let request of requests) {
14 // Extract the two users involved in the friend request
15 let user1 = request[0], user2 = request[1];
16
17 // If the users are already connected, the new friend request is automatically valid
18 if (findParent(user1) === findParent(user2)) {
19 answers.push(true);
20 } else {
21 // Assume the request is valid initially
22 let isValidRequest = true;
23
24 // Check all restrictions to see if the friend request violates any
25 for (let restriction of restrictions) {
26 let restrictedUser1 = restriction[0], restrictedUser2 = restriction[1];
27
28 // Check if accepting this friend request would violate a restriction
29 if ((findParent(user1) === findParent(restrictedUser1) && findParent(user2) === findParent(restrictedUser2)) ||
30 (findParent(user1) === findParent(restrictedUser2) && findParent(user2) === findParent(restrictedUser1))) {
31 isValidRequest = false;
32 break;
33 }
34 }
35
36 // Record the validity of the request
37 answers.push(isValidRequest);
38
39 // If the request is valid, unite the two sets
40 if (isValidRequest) {
41 parent[findParent(user1)] = findParent(user2);
42 }
43 }
44 }
45
46 // Return array of boolean values representing the validity of each request
47 return answers;
48}
49
50// Function to find the root of the set that element 'x' belongs to
51function findParent(x: number): number {
52 // Path compression: make each node directly point to the root
53 if (parent[x] !== x) {
54 parent[x] = findParent(parent[x]);
55 }
56 return parent[x];
57}
58
Time and Space Complexity
Time Complexity
The time complexity of the given code is primarily determined by two parts: the union-find operations and the restriction checks for each friend request.
-
The
find
function is a typical union-find operation with path compression. The amortized time complexity for eachfind
call isO(alpha(n))
, wherealpha
is the inverse Ackermann function, which grows very slowly and is considered almost constant in practice for all reasonable values ofn
. -
Each friend request involves checking all the restrictions. There are
r
restrictions, wherer
is the number of elements in therestrictions
list. For each request, the code loops through all restrictions, leading tor
calls to thefind
function in the worst case. -
Let
q
be the number of friend requests. For each request, there could be up tor
restriction checks, each of which could result in up to4
calls to thefind
function (2
pairs of friends to check for each restriction).
The worst-case time complexity can be expressed as O(q * r * alpha(n))
.
Space Complexity
The space complexity is determined by the storage for the parent pointers and the output list.
-
The parent array
p
has lengthn
, so the space complexity for the union-find data structure isO(n)
. -
Apart from the parent pointers, the space used by the restrictions, requests, and the answer list is determined by the input, which we don't count towards the extra space taken by the algorithm.
-
The
ans
list will containq
boolean values, whereq
is the number of requests.
Therefore, the overall space complexity of the algorithm is O(n + q)
, but since the space for the output list ans
is required for the result of the function, we generally don't count it as additional space complexity in an analysis. Thus, we can simply say the space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement recursion?
Recommended Readings
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we