{x}
blog image

Process Restricted Friend Requests

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 <= 1000
  • 0 <= restrictions.length <= 1000
  • restrictions[i].length == 2
  • 0 <= xi, yi <= n - 1
  • xi != yi
  • 1 <= requests.length <= 1000
  • requests[j].length == 2
  • 0 <= uj, vj <= n - 1
  • uj != vj

Solution Explanation: Process Restricted Friend Requests

This problem involves processing friend requests while adhering to restrictions. The optimal approach utilizes a Union-Find data structure.

Core Idea:

The Union-Find data structure efficiently tracks connected components (groups of friends). We initialize a parent array p where p[i] represents the parent node of person i in the Union-Find tree. Initially, each person is their own parent (representing no friendships).

For each friend request:

  1. Find: We use the find function (path compression optimized) to find the root (representative) of the connected component for each person in the request.

  2. Check Restriction: If the representatives are different (meaning they aren't already friends), we iterate through the restrictions. If a restriction prevents the friendship (i.e., one person is in the same group as one restricted person, and the other person is in the same group as the other restricted person), the request is denied.

  3. Union (if allowed): If the request is allowed, we unite the connected components of the two people using p[find(u)] = find(v) (or vice-versa), updating the Union-Find tree.

Time Complexity:

  • Initialization: O(n) to create the parent array.
  • Find Operation: O(α(n)) on average using path compression, where α(n) is the inverse Ackermann function, which is practically constant for all realistic input sizes.
  • Check Restriction: O(m) in the worst case for each request (m is the number of restrictions).
  • Union Operation: O(α(n)) on average.

Overall, the time complexity is dominated by checking restrictions for each request, resulting in O(q * m), where q is the number of requests. In the worst case, we might process all restrictions for every request.

Space Complexity:

O(n) to store the parent array and O(1) for other variables. Therefore, the space complexity is O(n).

Code Examples (Python):

class Solution:
    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:
        parent = list(range(n))
 
        def find(i):
            if parent[i] == i:
                return i
            parent[i] = find(parent[i])  # Path compression for efficiency
            return parent[i]
 
        def union(i, j):
            root_i = find(i)
            root_j = find(j)
            if root_i != root_j:
                parent[root_i] = root_j
 
        result = []
        for u, v in requests:
            root_u = find(u)
            root_v = find(v)
            allowed = True
            if root_u != root_v:  # Only check restrictions if not already friends
                for x, y in restrictions:
                    if (find(x) == root_u and find(y) == root_v) or \
                       (find(x) == root_v and find(y) == root_u):
                        allowed = False
                        break
            if allowed:
                union(u, v)
            result.append(allowed)
        return result

This Python code implements the Union-Find algorithm with path compression for efficiency, making it suitable even for larger inputs. The other languages (Java, C++, Go, TypeScript) would follow a very similar structure, adapting the syntax as needed. The fundamental algorithm remains the same.