#2076

Hard

LeetCode Problem Workspace

Process Restricted Friend Requests

Determine which friend requests can be accepted without violating direct or indirect restrictions using union-find logic.

union find graph

Problem Statement

You are given an integer n representing the number of people in a social network, labeled from 0 to n - 1. Initially, no one is friends with anyone else. Additionally, a 0-indexed array restrictions is provided, where each restrictions[i] = [xi, yi] indicates that person xi and person yi cannot become friends directly or indirectly through other friendships.

A list of friend requests is provided as a 0-indexed array requests, where requests[j] = [uj, vj] represents a request for person uj and person vj to become friends. Process each request in order and determine whether it can be accepted without violating any restrictions, returning a boolean array indicating the outcome for each request.

Examples

Example 1

Input: n = 3, restrictions = [[0,1]], requests = [[0,2],[2,1]]

Output: [true,false]

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]

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]

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 Approach

Use Union-Find to Track Components

Maintain a union-find structure to represent friend groups. Each group tracks which members are connected, enabling constant-time checks to see if two people belong to conflicting components before accepting a request.

Check Restrictions Efficiently

For each request, iterate over restrictions and check whether connecting the two people would merge groups that violate a restriction. This ensures indirect forbidden connections are detected without building the entire graph explicitly.

Update Friend Groups After Acceptance

If a request is valid, union the two people in the union-find structure. This updates components to reflect the new friendship and prepares for subsequent requests to be validated efficiently.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the number of requests times the number of restrictions, optimized using union-find with path compression. Space complexity is mainly the union-find arrays for parent and rank structures.

What Interviewers Usually Probe

Pay attention to indirect friendships that may violate restrictions.
Consider union-find optimizations for fast component lookups.
Clarify how restrictions affect both direct and indirect connections.

Common Pitfalls or Variants

Common pitfalls

Failing to account for indirect friendship violations through multiple connected people.
Updating union-find incorrectly, leading to incorrect future checks.
Assuming requests can always be accepted if no direct restriction exists.

Follow-up variants

Restrictions may be asymmetric, requiring careful union-find checks.
Requests can arrive in random order, increasing the importance of efficient checking.
The network could grow dynamically, testing union-find scaling under frequent updates.

FAQ

How does the union-find structure help with 'Process Restricted Friend Requests'?

Union-find allows you to track connected friend groups efficiently, making it easy to check if adding a friendship violates any restrictions indirectly.

What happens if a request violates a restriction?

The request is rejected, and the union-find structure is not updated, preventing indirect restricted friendships.

Can restrictions be checked in constant time?

By using union-find with path compression, you can approximate near-constant time checks for whether two people belong to conflicting groups.

Do accepted requests affect future checks?

Yes, each accepted request updates the union-find components, impacting whether subsequent requests are allowed.

What is the main failure mode in this problem?

Failing to detect indirect violations of restrictions when merging friend groups is the main source of errors.

terminal

Solution

Solution 1: Union-Find

We can use a union-find set to maintain the friend relationships, and then for each request, we determine whether it meets the restriction conditions.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

class Solution:
    def friendRequests(
        self, n: int, restrictions: List[List[int]], requests: List[List[int]]
    ) -> List[bool]:
        def find(x: int) -> int:
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        p = list(range(n))
        ans = []
        for u, v in requests:
            pu, pv = find(u), find(v)
            if pu == pv:
                ans.append(True)
            else:
                ok = True
                for x, y in restrictions:
                    px, py = find(x), find(y)
                    if (pu == px and pv == py) or (pu == py and pv == px):
                        ok = False
                        break
                ans.append(ok)
                if ok:
                    p[pu] = pv
        return ans

Continue Practicing

#2092 find all people with secret #1971 find if path exists in graph #2316 count unreachable pairs of nodes in an undirected graph