Count Unhappy Friends — LeetCode 1583 Python Solution
MediumArraySimulation
- Problem
- #1583
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You are given a list of preferences for n friends, where n is always even. For each person i, preferences[i] contains a list of friends sorted in the order of preference.
Example
- Input
- n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
- Output
- 2
- Explanation
- Friend 1 is unhappy because:
Python solution
Python
class Solution:
def unhappyFriends(
self, n: int, preferences: List[List[int]], pairs: List[List[int]]
) -> int:
d = [{x: j for j, x in enumerate(p)} for p in preferences]
p = {}
for x, y in pairs:
p[x] = y
p[y] = x
ans = 0
for x in range(n):
y = p[x]
for i in range(d[x][y]):
u = preferences[x][i]
v = p[u]
if d[u][x] < d[u][v]:
ans += 1
break
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n^2) |
| Space | O(n^2) auxiliary |
Related problems
LeetCode 495Teemo AttackingEasyLeetCode 985Sum of Even Numbers After QueriesMediumLeetCode 1389Create Target Array in the Given OrderEasyLeetCode 1409Queries on a Permutation With KeyMediumLeetCode 1503Last Moment Before All Ants Fall Out of a PlankMediumLeetCode 1535Find the Winner of an Array GameMedium
Frequently asked questions
- How hard is LeetCode 1583. Count Unhappy Friends?
- LeetCode 1583. Count Unhappy Friends is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1583. Count Unhappy Friends?
- The Python solution on this page runs in O(n^2).
- What is the space complexity of LeetCode 1583. Count Unhappy Friends?
- The Python solution on this page uses O(n^2) auxiliary space.
- What topics does LeetCode 1583. Count Unhappy Friends cover?
- LeetCode 1583. Count Unhappy Friends is tagged Array and Simulation on LeetCode.