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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Process Restricted Friend Requests

Number: 2198

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

There are n people (labeled 0 to n-1) and initially no friendships. Some pairs of people are restricted so that they cannot become friends either directly or indirectly. You are given a list of friendship requests. Process these requests in order and form friendships only when doing so will not indirectly connect any restricted pair. Even if the two users are already connected (directly or indirectly) then the request is considered successful. Return a boolean array indicating the success of each request.

Key Insights

  • Use the Union Find (Disjoint Set Union) data structure to efficiently manage connected components.
  • For each friendship request, check if merging the two components would violate any restriction.
  • To check a restriction, simulate the union by mapping both involved leaders (if they are being merged) to one common representative.
  • Revert or skip the union if any restricted pair would become connected.
  • The constraints are small (n, requests, restrictions up to 1000) so checking all restrictions per request is acceptable.

Space and Time Complexity

Time Complexity: O(R * M * α(n))
  R = number of requests, M = number of restrictions, and α(n) is the inverse Ackermann function (almost constant).
Space Complexity: O(n) for the union-find parent array (plus additional space for restrictions and requests).

Solution

We maintain a union-find (DSU) structure where each node has a parent pointer. For each friend request between u and v:

  1. Find their leaders.
  2. If they are already in the same group, the request is automatically successful.
  3. Otherwise, simulate a merge by assuming both groups are merged. For each restriction [x, y]:   - Compute the effective leader for x and y; if a leader equals either of the two merging leaders, treat it as the new common representative.   - If the effective leaders for x and y become equal after simulation, accepting the request would violate the restriction.
  4. If no violation is found, perform the union and mark the request as successful.
  5. Otherwise, reject the request.

This simulation ensures that merging u and v will not indirectly connect any pair that is restricted.

Code Solutions

# Python solution with detailed comments

class DSU:
    # Initialize DSU for n elements
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, x):
        # Path compression technique
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # Union by setting parent's representative of y to x
        self.parent[self.find(y)] = self.find(x)

def processRequests(n, restrictions, requests):
    dsu = DSU(n)
    result = []
    
    for u, v in requests:
        # Find current leaders for u and v.
        leaderU = dsu.find(u)
        leaderV = dsu.find(v)
        
        # If already in the same component, it's automatically successful.
        if leaderU == leaderV:
            result.append(True)
            continue
        
        # Assume we want to merge leaderV into leaderU.
        can_merge = True
        # Check each restriction for potential conflict
        for x, y in restrictions:
            # Find the current leaders for x and y.
            leaderX = dsu.find(x)
            leaderY = dsu.find(y)
            
            # Simulate the union:
            # If x's leader is one of the merging groups, then in the merged component the leader becomes leaderU.
            if leaderX == leaderU or leaderX == leaderV:
                simulatedLeaderX = leaderU
            else:
                simulatedLeaderX = leaderX
            
            # Similarly, assign simulated leader for y.
            if leaderY == leaderU or leaderY == leaderV:
                simulatedLeaderY = leaderU
            else:
                simulatedLeaderY = leaderY
            
            # If after the merge, restricted x and y become connected, mark merge as invalid.
            if simulatedLeaderX == simulatedLeaderY:
                can_merge = False
                break
        
        if can_merge:
            # Accept the request and union the two groups.
            dsu.union(leaderU, leaderV)
            result.append(True)
        else:
            # Do not merge; the request is rejected.
            result.append(False)
    
    return result

# Example usage:
if __name__ == "__main__":
    n = 3
    restrictions = [[0,1]]
    requests = [[0,2],[2,1]]
    print(processRequests(n, restrictions, requests))  # Expected output: [True, False]
← Back to All Questions