#1583

Count Unhappy Friends

specialist · 740 · lc medium +31 · verified · 62.5% accepted · 305 likes · top 64%

Description

You are given preferences for n friends (always even) sorted by preference order, and a pairs list of how they are matched. A friend x is unhappy if there exists another friend u such that x prefers u over their current partner and u also prefers x over their current partner. Return the total number of unhappy friends.

Example 1:

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:

- 1 is paired with 0 but prefers 3 over 0, and

- 3 prefers 1 over 2.

Friend 3 is unhappy because:

- 3 is paired with 2 but prefers 1 over 2, and

- 1 prefers 3 over 0.

Friends 0 and 2 are happy.

Example 2:

Input: n = 2, preferences = [[1], [0]], pairs = [[1, 0]]

Output: 0

Explanation: Both friends 0 and 1 are happy.

Example 3:

Input: n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]

Output: 4

Code

1

2

3

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int: