We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Process Restricted Friend Requests

Difficulty: Hard

Problem Description

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, 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.

Key Insights

  • The problem involves managing friendships with restrictions, making it a graph problem.
  • Union-Find (Disjoint Set Union) is a suitable approach to keep track of connected components (friends).
  • Each successful request can either connect two people directly or be blocked due to indirect restrictions.
  • We need to check not only direct restrictions but also indirect connections through existing friends.

Space and Time Complexity

Time Complexity: O(m * α(n)), where m is the number of requests and α is the Inverse Ackermann function, which grows very slowly. Space Complexity: O(n + r), where n is the number of people and r is the number of restrictions.

Solution

The problem can be solved using the Union-Find data structure to efficiently manage connected components of friends. We will maintain a parent array to represent the leader of each person's set and a rank array to optimize union operations. For each request, we will check if adding the new friendship would violate any restrictions by temporarily adding the friendship and checking the connections. If there are no violations, we finalize the friendship by performing a union operation.

Code Solutions

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [1] * size

    def find(self, person):
        if self.parent[person] != person:
            self.parent[person] = self.find(self.parent[person])  # Path compression
        return self.parent[person]

    def union(self, person1, person2):
        root1 = self.find(person1)
        root2 = self.find(person2)
        if root1 != root2:
            if self.rank[root1] > self.rank[root2]:
                self.parent[root2] = root1
            elif self.rank[root1] < self.rank[root2]:
                self.parent[root1] = root2
            else:
                self.parent[root2] = root1
                self.rank[root1] += 1

def canBeFriends(n, restrictions, requests):
    uf = UnionFind(n)
    result = []
    
    for u, v in requests:
        # Temporarily union u and v
        uf.union(u, v)
        
        # Check restrictions
        can_request = True
        for x, y in restrictions:
            if uf.find(x) == uf.find(y):  # If x and y are connected
                can_request = False
                break
        
        # If the request is not valid, revert the union
        if not can_request:
            result.append(False)
            # Revert union is not easy in classic Union-Find, so we won't actually revert
            # We will just not finalize the union
        else:
            result.append(True)
    
    return result
← Back to All Questions