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.

  1. 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))
  2. 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 subsequent find() operations.

    1def find(x):
    2    if p[x] != x:
    3        p[x] = find(p[x])
    4    return p[x]
  3. Processing Friend Requests: Friend requests are processed in the given order. For each friend request between u and v, we perform the following:

    • Check if u and v 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 if u or v is restricted with the other by comparing their representatives with x and y. 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)
  4. 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 Evaluator

Example 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:

  1. Parent Array Initialization: Initially, the parent array p is [0, 1, 2, 3, 4], with each person as their own parent.

  2. Find Function: This will be used to find the representatives of each person's set as we process the requests.

  3. Processing Friend Requests:

    • Request (0, 2): Since find(0) == 0 and find(2) == 2, they are not in the same set. There are no restrictions involving 0 and 2, so they can be friends. We perform the union by setting p[find(0)] = find(2), so now p[0] = 2. The parent array is now [2, 1, 2, 3, 4].

    • Request (1, 2): Now, find(1) == 1 and find(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) and find(1) are both 2), 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 and find(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 involves 2 and 3, and since they are not in the same set (find(2) == 2 and find(3) == 3), they can be friends. We perform the union p[find(2)] = find(3), and the parent array becomes [2, 2, 3, 3, 4].

  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 each find call is O(alpha(n)), where alpha is the inverse Ackermann function, which grows very slowly and is considered almost constant in practice for all reasonable values of n.

  • Each friend request involves checking all the restrictions. There are r restrictions, where r is the number of elements in the restrictions list. For each request, the code loops through all restrictions, leading to r calls to the find function in the worst case.

  • Let q be the number of friend requests. For each request, there could be up to r restriction checks, each of which could result in up to 4 calls to the find 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 length n, so the space complexity for the union-find data structure is O(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 contain q boolean values, where q 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used to implement recursion?


Recommended Readings