HardNo. 2076
Process Restricted Friend Requests — LeetCode 2076 Python Solution
- Pattern
- Union-Find
- Topics
- Union Find, Graph
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given an integer n indicating the number of people in a network. Each person is labeled from 0 to n - 1.
Example
- 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.
Python solution
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 ansComplexity
- Time
- O(q × m × log(n))
- Space · auxiliary
- O(n)
Pattern: Union-Find
Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2076. Process Restricted Friend Requests is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.
The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
| 0684 | Redundant Connection | Medium |
| 0685 | Redundant Connection II | Hard |
| 0785 | Is Graph Bipartite? | Medium |
| 0886 | Possible Bipartition | Medium |
Frequently asked questions
- How hard is LeetCode 2076. Process Restricted Friend Requests?
LeetCode 2076. Process Restricted Friend Requests is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2076. Process Restricted Friend Requests?
The Python solution on this page runs in O(q × m × log(n)).
- What is the space complexity of LeetCode 2076. Process Restricted Friend Requests?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2076. Process Restricted Friend Requests cover?
LeetCode 2076. Process Restricted Friend Requests is tagged Union Find and Graph on LeetCode.