1583. Count Unhappy Friends
Problem Description
The problem presents a scenario of n
friends paired with each other, where n
is an even number. Each friend has a preference order list for all other friends, indicating who they would rather be paired with, in descending order of preference.
The friends have been matched into pairs based on the pairs
list provided. However, not all friends may be content with their pairing. A friend x
is considered unhappy if x
prefers someone else u
over their current partner y
, and at the same time u
prefers x
over their own partner v
. The aim here is to calculate the total number of unhappy friends.
Intuition
The intuition behind the solution involves the following key steps:
-
Convert Preferences to Indexes: To expedite lookup operations, it is advantageous to convert each friend's preferences list, which stores friends' IDs, into a dictionary where keys are the friend IDs and values are their corresponding preference rankings. This allows us to quickly determine the ranking of one friend over another in anyoneās preference list.
-
Store Pairing Information Efficiently: Similarly, we use another dictionary to store each friend's current partner from the pairing list. This makes it fast and easy to find out who is paired with whom at any point.
-
Check for Unhappy Friends: Iterate over each friend
x
, and within that, iterate overx
's preference list up until (but not including) the current partnery
. For each friendu
in the preference list who is preferred overy
, we check ifu
also prefersx
over their own partnerv
. If such au
exists,x
is unhappy, and we add to our unhappy friends count. -
Count: After processing all friends, the count of unhappy friends gives us the desired answer.
This approach is efficient as it avoids unnecessary comparisons; we only consider friends who are ranked higher than the current partners and hence have the potential to cause unhappiness.
Solution Approach
The core implementation of the solution follows a precise and logical methodology, incorporating specific data structures and algorithms:
-
Dictionary of Preferences' Ranks: A list of dictionaries
d
is created where each dictionary corresponds to a friend and holds that friend's preferences with preference rankings as values. This transforms a list of preferred friends for each person into a structure that allows for O(1) time lookup to find out how muchi
prefersp
over others.1d = [{p: i for i, p in enumerate(v)} for v in preferences]
This list comprehension iterates over each friendās preferences list
v
, and for each friend's preferences, it generates a dictionary that maps the friend's IDp
to its preference ranki
. -
Pairings Dictionary: Another dictionary
p
is created to hold the current pairings based on thepairs
list. This dictionary is used to find out directly who is paired with whom.1p = {} 2for x, y in pairs: 3 p[x] = y 4 p[y] = x
-
Determine Unhappiness: An integer
ans
is set up to keep count of the number of unhappy friends.The solution iterates over each friend
x
and checks the list of their preferred friends (up until their current partnery
) to see if there exists someone they prefer more (u
) who also prefers them back over their own partnerv
.1ans = 0 2for x in range(n): 3 y = p[x] 4 ans += any(d[u][x] < d[u][p[u]] for u in preferences[x][: d[x][y]])
Here,
d[x][y]
finds the ranking ofy
inx
's preferences. The slicepreferences[x][: d[x][y]]
gets all friends preferred more byx
thany
. For each such friendu
, ifd[u][x] < d[u][p[u]]
, it meansu
prefersx
over their current partnerp[u]
. Theany
function checks if there's any suchu
that satisfies this condition. If yes,x
is unhappy. -
Return Answer: After iterating over all friends and accumulating the count of unhappy ones, the final value of
ans
is returned.
The algorithm is efficient due to the use of dictionaries for quick lookups and the limited iteration up to the current pair, avoiding unnecessary comparison checks.
1return ans
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through a small example to illustrate the solution approach. Assume we have 4 friends (with IDs 0, 1, 2, and 3) and their preference listings, as well as their current pairings.
Suppose the friends' preference lists are as follows:
- Friend 0 prefers: [1, 2, 3]
- Friend 1 prefers: [2, 0, 3]
- Friend 2 prefers: [1, 0, 3]
- Friend 3 prefers: [0, 1, 2]
And they are paired like this:
- Pairings: [(0, 1), (2, 3)]
To solve this problem with the proposed solution approach:
-
We first convert the preference lists into dictionaries with rankings for O(1) lookup times.
For friend 0:
{1: 0, 2: 1, 3: 2}
For friend 1:{2: 0, 0: 1, 3: 2}
For friend 2:{1: 0, 0: 1, 3: 2}
For friend 3:{0: 0, 1: 1, 2: 2}
-
Next, we create a dictionary to represent the pairings:
{0: 1, 1: 0, 2: 3, 3: 2}
-
Now we determine if there are any unhappy friends. We proceed as follows:
- Check friend 0: Paired with friend 1. Friend 0 prefers friend 2 over 1 (from their preference list), but friend 2, who is paired with friend 3, prefers friend 1 over 0. Therefore, friend 0 is not unhappy.
- Check friend 1: Paired with friend 0. Friend 1 prefers friend 2 over 0 and friend 2 also prefers friend 1 over their partner friend 3, thus friend 1 is unhappy.
- Check friend 2: Paired with friend 3. Friend 2 prefers friend 1 over 3, and we already know that friend 1 prefers friend 2 over their current partner (friend 0). Therefore, friend 2 is unhappy.
- Check friend 3: Paired with friend 2. Friend 3 prefers friend 0 over 2, but friend 0 prefers friend 1 over friend 3, hence friend 3 is not unhappy.
So from our example, friends 1 and 2 are unhappy.
-
Lastly, we return the count of unhappy friends which is 2 in this case.
By following the outlined solution steps, we efficiently find the total number of unhappy friends without unnecessary comparisons and in a manner that is easy to follow and implement.
Solution Implementation
1from typing import List
2
3class Solution:
4 def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
5 # Create a dictionary to store preferences index for quick lookup.
6 # `preference_rankings` is a list of dictionaries for each person,
7 # mapping their friend to the ranking of that friend in their preference.
8 preference_rankings = [{friend: rank for rank, friend in enumerate(prefs)} for prefs in preferences]
9
10 # Create a dictionary to store each person's paired friend.
11 paired_friends = {}
12 for x, y in pairs:
13 paired_friends[x] = y
14 paired_friends[y] = x
15
16 # Initialize the count of unhappy friends.
17 unhappy_count = 0
18
19 # Iterate through each person to determine if they are unhappy.
20 for x in range(n):
21 # The paired friend of `x`.
22 y = paired_friends[x]
23
24 # Check if there exists a person 'u' who is a better preference for 'x'
25 # than 'x's paired friend 'y'. We do this by checking the preference
26 # rankings in the subset of preferences before 'y'.
27 is_unhappy = any(
28 preference_rankings[u][x] < preference_rankings[u][paired_friends[u]]
29 for u in preferences[x][: preference_rankings[x][y]]
30 )
31
32 # If such a person 'u' exists, increment the unhappy count.
33 if is_unhappy:
34 unhappy_count += 1
35
36 return unhappy_count
37
1class Solution {
2 public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
3 // Distance matrix indicating how strongly each friend prefers other friends
4 int[][] preferenceDistances = new int[n][n];
5 // Fill the preference distance matrix with preference rankings
6 for (int i = 0; i < n; ++i) {
7 for (int j = 0; j < n - 1; ++j) {
8 preferenceDistances[i][preferences[i][j]] = j;
9 }
10 }
11
12 // Pairing array where the index is the friend and the value is their pair
13 int[] pairings = new int[n];
14 // Fill the pairings array based on the given pairs
15 for (int[] pair : pairs) {
16 int friend1 = pair[0], friend2 = pair[1];
17 pairings[friend1] = friend2;
18 pairings[friend2] = friend1;
19 }
20
21 // Counter for unhappy friends
22 int unhappyCount = 0;
23 // Iterate over all friends to determine unhappiness
24 for (int friendX = 0; friendX < n; ++friendX) {
25 int friendY = pairings[friendX];
26 boolean isUnhappy = false; // Flag to check if the current friend is unhappy
27
28 // Check if there exists a friend that friendX ranks higher than their current paired friendY
29 for (int i = 0; i < preferenceDistances[friendX][friendY]; ++i) {
30 int otherFriend = preferences[friendX][i];
31 // Check if the other friend (u) prefers friendX over their own pairing
32 if (preferenceDistances[otherFriend][friendX] < preferenceDistances[otherFriend][pairings[otherFriend]]) {
33 isUnhappy = true;
34 break;
35 }
36 }
37 // Increment unhappyCount if friendX is found to be unhappy
38 if (isUnhappy) {
39 unhappyCount++;
40 }
41 }
42 return unhappyCount; // Return the total number of unhappy friends
43 }
44}
45
1class Solution {
2public:
3 // Function to calculate the number of unhappy friends
4 int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
5 // Declare a 2D array to store the preference rank
6 int preferenceRank[n][n];
7 // Array to store the pair partner for each person
8 int pairPartner[n];
9
10 // Initialize the preference ranks for each friend
11 for (int i = 0; i < n; ++i) {
12 for (int j = 0; j < n - 1; ++j) {
13 preferenceRank[i][preferences[i][j]] = j;
14 }
15 }
16
17 // Assign the pair partners based on the given pairs
18 for (auto& pair : pairs) {
19 int friendOne = pair[0], friendTwo = pair[1];
20 pairPartner[friendOne] = friendTwo;
21 pairPartner[friendTwo] = friendOne;
22 }
23
24 int unhappyCount = 0; // Counter for unhappy friends
25
26 // Iterate through each friend to check unhappiness
27 for (int friendX = 0; friendX < n; ++friendX) {
28 int friendY = pairPartner[friendX]; // Partner of the current friend
29 bool isUnhappy = false; // Flag to check if the current friend is unhappy
30
31 // Check whether there is a person that friendX prefers over friendY
32 for (int i = 0; i < preferenceRank[friendX][friendY]; ++i) {
33 int preferredFriend = preferences[friendX][i];
34 // If preferredFriend prefers friendX over their current partner, friendX is unhappy
35 if (preferenceRank[preferredFriend][friendX] < preferenceRank[preferredFriend][pairPartner[preferredFriend]]) {
36 isUnhappy = true;
37 break; // No need to check the rest since friendX is already unhappy
38 }
39 }
40
41 // If friendX is found to be unhappy, increment the unhappy count
42 if (isUnhappy) {
43 unhappyCount++;
44 }
45 }
46
47 // Return the final count of unhappy friends
48 return unhappyCount;
49 }
50};
51
1// Define a type for the preference array that's used multiple times
2type Preferences = number[][];
3
4// Function to initialize the preference ranks for each friend
5function initializePreferenceRanks(n: number, preferences: Preferences): number[][] {
6 const preferenceRanks: number[][] = Array.from({ length: n }, () => Array(n).fill(-1));
7 for (let i = 0; i < n; ++i) {
8 for (let j = 0; j < n - 1; ++j) {
9 preferenceRanks[i][preferences[i][j]] = j;
10 }
11 }
12 return preferenceRanks;
13}
14
15// Function to assign pair partners based on the given pairs
16function assignPairPartners(pairs: Preferences): number[] {
17 const pairPartners: number[] = Array(pairs.length * 2);
18 for (const pair of pairs) {
19 const [friendOne, friendTwo] = pair;
20 pairPartners[friendOne] = friendTwo;
21 pairPartners[friendTwo] = friendOne;
22 }
23 return pairPartners;
24}
25
26// Function to calculate the number of unhappy friends
27function unhappyFriends(n: number, preferences: Preferences, pairs: Preferences): number {
28 const preferenceRanks = initializePreferenceRanks(n, preferences);
29 const pairPartners = assignPairPartners(pairs);
30 let unhappyCount = 0; // Counter for unhappy friends
31
32 for (let friendX = 0; friendX < n; ++friendX) {
33 const friendY = pairPartners[friendX]; // Partner of the current friend
34 let isUnhappy = false; // Flag to check if the current friend is unhappy
35
36 // Check whether there is a person that friendX prefers over friendY
37 for (let i = 0; i < preferenceRanks[friendX][friendY]; ++i) {
38 const preferredFriend = preferences[friendX][i];
39 // If preferredFriend prefers friendX over their current partner, friendX is unhappy
40 if (preferenceRanks[preferredFriend][friendX] < preferenceRanks[preferredFriend][pairPartners[preferredFriend]]) {
41 isUnhappy = true;
42 break; // No need to check the rest since friendX is already unhappy
43 }
44 }
45
46 // Increment the unhappy count if friendX is found to be unhappy
47 if (isUnhappy) {
48 unhappyCount++;
49 }
50 }
51
52 return unhappyCount; // Return the final count of unhappy friends
53}
54
Time and Space Complexity
Time Complexity
The time complexity of the code is determined by several factors:
-
The comprehension used to create the dictionary
d
takesO(n^2)
time, wheren
is the number of friends, because the preferences list for each friend is of lengthn-1
, and there aren
such lists. -
The loop setting up the
p
dictionary runs forO(n/2)
pairs, which simplifies toO(n)
because each pair is processed exactly once. -
The outer loop to calculate
ans
traversesn
friends, which gives usO(n)
. -
Inside this outer loop, there's an
any
function call on a generator expression. In the worst case, it scans throughn-2
elements (since one element is the friend themselves, and another is the paired friend). Therefore, this gives usO(n-2)
for each friend.
When you put these factors together, the worst-case time complexity is O(n^2)
due to the initial comprehension for the dictionary d
. All the other operations, although they depend on n
, don't involve nested loops over n
, so they don't contribute a higher order term than n^2
.
Thus, the final time complexity is O(n^2)
.
Space Complexity
Now let's analyze the space complexity:
-
The
d
dictionary stores preferences for each of then
friends using a dictionary, so it takesO(n^2)
space. -
The
p
dictionary holds the paired friends' information, withn
entries (two entries for each pair). Thus, it consumesO(n)
space. -
The space for
ans
and loop variables is constant,O(1)
.
Adding these together, the dominant term is the O(n^2)
space required for the d
dictionary. Thus, the total space complexity is also O(n^2)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used in a depth first search?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
0 : 1,2,3 1 : 3,2,0 2 : 3,1,0 3 : 1,2,0
And given pairs are = [[0, 1], [2, 3]]
0 is happy, because 1 is the first preferece.
1 is unhappy, because 3 is its prior preference.
2 is happy because 3 is its first preference.
3 is also unhappy because 1 is its preferece ans.
Check friend 0: Paired with friend 1. Friend 0 prefers friend 2 over 1 (from their preference list), but friend 2, who is paired with friend 3, prefers friend 1 over 0. Therefore, friend 0 is not unhappy. This is not correct