Tap here to switch tabs
Problem
Submissions

Problem: Count Unhappy Friends

Count Unhappy Friends asks you to examine ranked preference lists and fixed pairs, then count friends who prefer someone else and are preferred by that person in return.

Statement

You are given an integer n, representing the number of friends labeled from 00 to n−1n - 1. You are also given an array preferences, where preferences[i] is a list of all other friends sorted in order of preference, from most preferred to least preferred.

The friends are divided into pairs represented by a 2D2 {D} array pairs, where pairs[i] = [x_i, y_i] indicates that friend x_i is paired with friend y_i. Each friend belongs to exactly one pair.

A friend x is unhappy if x is paired with y, and there exists another friend u who is paired with v such that both of the following conditions hold:

  • x prefers u over y

  • u prefers x over v

Return the total number of unhappy friends.

Constraints:

  • 2≤2 \leq n ≤500\leq 500

  • n is even.

  • preferences.length =n= n

  • preferences[i].length =n−1= n - 1

  • 0≤0 \leq preferences[i][j] ≤n−1\leq n - 1

  • preferences[i] does not contain i.

  • All values in preferences[i] are unique.

  • pairs.length =n/2= n / 2

  • pairs[i].length =2= 2

  • x_i ≠\neq y_i

  • 0≤0 \leq x_i, y_i ≤n−1\leq n - 1

  • Each person is contained in exactly one pair.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Unhappy Friends

Count Unhappy Friends asks you to examine ranked preference lists and fixed pairs, then count friends who prefer someone else and are preferred by that person in return.

Statement

You are given an integer n, representing the number of friends labeled from 00 to n−1n - 1. You are also given an array preferences, where preferences[i] is a list of all other friends sorted in order of preference, from most preferred to least preferred.

The friends are divided into pairs represented by a 2D2 {D} array pairs, where pairs[i] = [x_i, y_i] indicates that friend x_i is paired with friend y_i. Each friend belongs to exactly one pair.

A friend x is unhappy if x is paired with y, and there exists another friend u who is paired with v such that both of the following conditions hold:

  • x prefers u over y

  • u prefers x over v

Return the total number of unhappy friends.

Constraints:

  • 2≤2 \leq n ≤500\leq 500

  • n is even.

  • preferences.length =n= n

  • preferences[i].length =n−1= n - 1

  • 0≤0 \leq preferences[i][j] ≤n−1\leq n - 1

  • preferences[i] does not contain i.

  • All values in preferences[i] are unique.

  • pairs.length =n/2= n / 2

  • pairs[i].length =2= 2

  • x_i ≠\neq y_i

  • 0≤0 \leq x_i, y_i ≤n−1\leq n - 1

  • Each person is contained in exactly one pair.