1583. Count Unhappy Friends

MediumArraySimulation
Leetcode Link

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:

  1. 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.

  2. 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.

  3. Check for Unhappy Friends: Iterate over each friend x, and within that, iterate over x's preference list up until (but not including) the current partner y. For each friend u in the preference list who is preferred over y, we check if u also prefers x over their own partner v. If such a u exists, x is unhappy, and we add to our unhappy friends count.

  4. 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:

  1. 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 much i prefers p 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 ID p to its preference rank i.

  2. Pairings Dictionary: Another dictionary p is created to hold the current pairings based on the pairs 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
  3. 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 partner y) to see if there exists someone they prefer more (u) who also prefers them back over their own partner v.

    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 of y in x's preferences. The slice preferences[x][: d[x][y]] gets all friends preferred more by x than y. For each such friend u, if d[u][x] < d[u][p[u]], it means u prefers x over their current partner p[u]. The any function checks if there's any such u that satisfies this condition. If yes, x is unhappy.

  4. 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 Evaluator

Example 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:

  1. 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}

  2. Next, we create a dictionary to represent the pairings: {0: 1, 1: 0, 2: 3, 3: 2}

  3. 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.

  4. 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:

  1. The comprehension used to create the dictionary d takes O(n^2) time, where n is the number of friends, because the preferences list for each friend is of length n-1, and there are n such lists.

  2. The loop setting up the p dictionary runs for O(n/2) pairs, which simplifies to O(n) because each pair is processed exactly once.

  3. The outer loop to calculate ans traverses n friends, which gives us O(n).

  4. Inside this outer loop, there's an any function call on a generator expression. In the worst case, it scans through n-2 elements (since one element is the friend themselves, and another is the paired friend). Therefore, this gives us O(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:

  1. The d dictionary stores preferences for each of the n friends using a dictionary, so it takes O(n^2) space.

  2. The p dictionary holds the paired friends' information, with n entries (two entries for each pair). Thus, it consumes O(n) space.

  3. 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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which data structure is used in a depth first search?


Recommended Readings

Christophe

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.

Tue Jul 16 2024
Cedric Chen

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

Tue Jun 25 2024