Show problems as
Classic problem #1583MediumArraySimulation

Count Unhappy Friends

Real-world version: Restless Deckhands on Paired Shifts
Tracked in this browser only
Read Count Unhappy Friends on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A crew of n deckhands is split into shift duos. preferences[i] lists every other deckhand in the order deckhand i would rather work with them, best first, so it holds n - 1 names and never names i. pairs gives the duos, and every deckhand appears in exactly one duo.

Deckhand a, paired with b, is restless when some deckhand c, paired with d, satisfies both of these at once:

  • a would rather work with c than with b
  • c would rather work with a than with d

Return how many deckhands are restless.

Examples

Example 1

Input
n = 6, preferences = [[2, 1, 3, 4, 5], [3, 0, 2, 4, 5], [0, 3, 1, 4, 5], [1, 2, 0, 4, 5], [5, 0, 1, 2, 3], [4, 0, 1, 2, 3]], pairs = [[0, 1], [2, 3], [4, 5]]
Output
4

Deckhands 0 and 2 top each other's lists yet are paired elsewhere, and so do 1 and 3, which leaves all four of them restless. Deckhands 4 and 5 are each other's first choice and are already paired, so neither is.

Example 2

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

Deckhand 0 would rather work with 2 than with 1, and 2 would rather work with 0 than with 3, so both are restless. Deckhands 1 and 3 already have their first choice.

Example 3

Input
n = 6, preferences = [[1, 2, 3, 4, 5], [0, 2, 3, 4, 5], [3, 0, 1, 4, 5], [2, 0, 1, 4, 5], [5, 0, 1, 2, 3], [4, 0, 1, 2, 3]], pairs = [[0, 1], [2, 3], [4, 5]]
Output
0

Every deckhand is paired with the one at the top of their own list, so no swap could suit both sides.

Constraints

  • 2 <= n <= 500
  • n is even
  • preferences.length == n
  • preferences[i].length == n - 1
  • 0 <= preferences[i][j] <= n - 1
  • preferences[i] never names i
  • The entries of preferences[i] are all different
  • pairs.length == n / 2
  • pairs[i].length == 2
  • The two deckhands in a duo are different
  • 0 <= pairs[i][0] <= n - 1
  • 0 <= pairs[i][1] <= n - 1
  • Every deckhand appears in exactly one duo

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def unhappy_friends(n: int, preferences: list[list[int]], pairs: list[list[int]]) -> int:
Java
public int unhappyFriends(int n, int[][] preferences, int[][] pairs)

More on the same topics