Process Restricted Friend Requests — LeetCode 2076 Python Solution
HardUnion FindGraph
- Problem
- #2076
- Pattern
- Union-Find
- 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
Python
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
| Measure | Complexity |
|---|---|
| Time | O(q \times m \times \log(n)) |
| Space | O(n) auxiliary |
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
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 \times m \times \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.