Skip to main content
Talentd

Process Restricted Friend Requests - Solution & Explanation

HardUnion FindGraph15 min readAsked at: Uber, Google
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You have n users, a list of friendship restrictions, and a sequence of friend requests. Each request asks whether two users can become friends. A request is valid only if accepting it does not indirectly connect any pair of users that are restricted from being in the same friend group.

Approach 1: Graph Check per Request (Brute Force) (Time: O(r * (n + e)), Space: O(n + e))

Model the accepted friendships as an undirected graph. For every request (u, v), temporarily assume the edge exists and check whether any restricted pair becomes connected. You can run a DFS or BFS to verify if the endpoints of a restricted pair fall into the same connected component. If a violation appears, reject the request; otherwise permanently add the edge. This approach is straightforward but inefficient because each request may trigger a full graph traversal.

Approach 2: Union-Find with Path Compression (Time: O(r * m * α(n)), Space: O(n))

Use a Disjoint Set Union structure to maintain connected components of friends. When a request (u, v) arrives, first find their current roots using path compression. If both users already share the same root, the request is automatically valid. Otherwise, scan the restriction list and check whether merging the two components would cause a restricted pair to end up in the same set. This happens if one restricted user belongs to the root of u and the other belongs to the root of v. If no conflict exists, union the two sets. DSU makes component lookups nearly constant with the inverse Ackermann factor α(n).

The key insight is that restrictions apply to entire components, not individual nodes once friendships accumulate. Tracking components with Union-Find avoids repeated graph traversals and keeps connectivity updates efficient. The restriction validation step simply compares roots instead of exploring edges.

Recommended for interviews: Union-Find with path compression. The brute-force graph approach demonstrates understanding of connectivity constraints, but the DSU solution shows strong knowledge of dynamic connectivity problems in graph systems. Interviewers typically expect the Union-Find design because it scales well with many requests.

Approach 1: Approach using Union-Find with Path Compression

The problem can be solved using the Union-Find data structure, also known as Disjoint Set Union (DSU). We use path compression to optimize the find operation. The goal is to manage dynamic connectivity among people, ensuring that no restricted indirect connections are formed.

Each person starts as their own component. To process a friendship request, we first check if making the friends would violate any existing restriction by checking their connected components. If it's safe (meaning they are not indirectly restricted), we use union to merge the two components.

The C implementation defines find and unionSets functions to manage connected components. In processFriendRequests(), we iterate over each request and check if the associated friendship is safe by comparing their root components with the restricted pairs. If safe, we merge the friend groups, else decline the request.

Code

CPythonJava

C

Python

Java

Complexity

Time Complexity: O((n + m) * α(n)) where α(n) is the inverse Ackermann function, very small and close to constant for practical inputs.
Space Complexity: O(n) for storing parent and rank arrays.

Try this approach in the editor →

Approach 2: 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.

For the two people (u, v) in the current request, if they are already friends, then the request can be directly accepted; otherwise, we traverse the restriction conditions. If there exists a restriction condition (x, y) such that u and x are friends and v and y are friends, or u and y are friends and v and x are friends, then the request cannot be accepted.

The time complexity is O(q times m times log(n)), and the space complexity is O(n). Where q and m are the number of requests and the number of restriction conditions respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach using Union-Find with Path Compression

Time Complexity: O((n + m) * α(n)) where α(n) is the inverse Ackermann function, very small and close to constant for practical inputs.
Space Complexity: O(n) for storing parent and rank arrays.

Union-Find—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Graph traversal check per requestO(r * (n + e))O(n + e)Useful for understanding the constraint logic or when request count is very small
Union-Find with path compressionO(r * m * α(n))O(n)Best general solution for large inputs with many friend requests

Video Solution

2076. Process Restricted Friend Requests | Leetcode Weekly Contest 267 | Graphs | DSU | DFS | DSA • Tejpratap Pandey • 827 views views

Watch 4 more video solutions →

Frequently Asked Questions

Is Process Restricted Friend Requests easy or hard?
Process Restricted Friend Requests is classified as Hard because it combines Union-Find with constraint validation across components. The challenge lies in recognizing that restrictions apply to entire connected groups rather than individual users.
Process Restricted Friend Requests Python/Java solution
The typical implementation uses a Union-Find class with parent arrays and path compression. For each request, compute the roots of both users and verify restrictions before performing a union. The same logic works across Python, Java, and C implementations.
How to solve Process Restricted Friend Requests in O(n)?
Use a Union-Find data structure to track connected components. For each request, find the roots of both users and verify that merging them will not place any restricted pair in the same component. If no restriction is violated, union the two sets and accept the request.
What is the best approach for Process Restricted Friend Requests?
Union-Find (Disjoint Set Union) with path compression is the most efficient approach. It keeps track of connected friend groups and checks whether merging two groups would violate any restriction. Each request performs near-constant time root lookups and scans the restriction list to detect conflicts.
Is Process Restricted Friend Requests asked at Google/Amazon/Meta?
Problems involving Union-Find and dynamic connectivity frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests understanding of disjoint sets, graph connectivity, and constraint validation during incremental updates.
What data structure is used in Process Restricted Friend Requests?
The core data structure is Disjoint Set Union (Union-Find). It efficiently tracks which users belong to the same friend group and supports fast union and find operations using path compression.
What is the time complexity of Process Restricted Friend Requests?
The optimized Union-Find solution runs in O(r * m * α(n)) time where r is the number of requests, m is the number of restrictions, and α(n) is the inverse Ackermann function from path compression. Space complexity is O(n) for the parent array storing the disjoint sets.

Ready to solve this problem?

Practice Process Restricted Friend Requests with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Employees to Be Invited to a Meeting

Next

Number of Islands II