Leetcode 1583. Count Unhappy Friends

Problem

Given a group of friends where each person has a list of friends they prefer to be paired with, we need to figure out how many people are unhappy with their pair. A friend, x, is unhappy if they are paired with y but actually prefer to be paired with someone else, u, and u also prefers x over whoever they are paired with, v. The objective is to return the number of unhappy friends.

To illustrate with an example: If we have 4 friends (0, 1, 2, 3) with the following preference lists: Friend 0 prefers to be paired with [1, 2, 3] Friend 1 prefers to be paired with [3, 2, 0] Friend 2 prefers to be paired with [3, 1, 0] Friend 3 prefers to be paired with [1, 2, 0]

And the pairs are: [0, 1], [2, 3]

Friend 1 is unhappy because they're paired with 0 but prefers 3, and 3 also prefers 1 over 2. Similarly, Friend 3 is unhappy because they're paired with 2 but prefers 1, and 1 also prefers 3 over 0. So the output would be 2 (i.e., 2 unhappy friends).

Solution Approach

In order to identify the number of unhappy friends, we can iterate over all the pairs. For each pair (x, y), we will check all the friends u higher in x's preferences than y i.e., anyone x prefers over y. If u prefers x over their partner v, then x is unhappy.

It is efficient to use a dictionary data structure to store the list of preferences

The solutions follow similar logic but use different syntax in accordance with the respective programming language.

Java Solution:

1
2java
3class Solution {
4  public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
5    int ans = 0;
6    int[] matches = new int[n];
7    int[][] prefer = new int[n][n];
8
9    // Assign pair index using pairs
10    for (int[] pair : pairs) {
11      int x = pair[0];
12      int y = pair[1];
13      matches[x] = y;
14      matches[y] = x;
15    }
16
17    // assign prefereness index 
18    for (int i = 0; i < n; ++i)
19      for (int j = 0; j < n - 1; ++j)
20        prefer[i][preferences[i][j]] = j;
21    
22    // Iterate over all friends
23    for (int x = 0; x < n; ++x)
24      for (int u : preferences[x]) {
25        int y = matches[x];
26        int v = matches[u];
27        if (prefer[x][u] < prefer[x][y] && prefer[u][x] < prefer[u][v]) {
28          ++ans;
29          break;
30        }
31      }
32
33    return ans;
34  }
35}

Python Solution:

1
2python
3from collections import defaultdict
4
5class Solution:
6  def unhappyFriends(self, n, preferences, pairs):
7    ans = 0;
8    matches = [0]*n
9    prefer = defaultdict(dict)
10
11    # Assign pair index using pairs
12    for pair in pairs:
13      x, y = pair
14      matches[x] = y
15      matches[y] = x
16
17    # Assign prefereness index
18    for i in range(n):
19      for j in range(n - 1):
20        prefer[i][preferences[i][j]] = j
21
22    # Iterate over all friends
23    for x in range(n):
24      for u, _ in prefer[x].items():
25        y = matches[x]
26        v = matches[u]
27        if prefer[x][u] < prefer[x][y] and prefer[u][x] < prefer[u][v]:
28          ans += 1
29          break
30          
31    return ans

JavaScript Solution:

1
2javascript
3var unhappyFriends = function(n, preferences, pairs) {
4    let ans = 0;
5    let matches = new Array(n).fill(0);
6    let prefer = new Array(n).fill(0).map(() => ({}));
7  
8    // Assign pair index using pairs
9    for (let pair of pairs) {
10      let x = pair[0];
11      let y = pair[1];
12      matches[x] = y;
13      matches[y] = x;
14    }
15  
16    // assign prefereness index 
17    for (let i = 0; i < n; ++i)
18      for (let j = 0; j < n - 1; ++j)
19        prefer[i][preferences[i][j]] = j;
20    
21    // Iterate over all friends
22    for (let x = 0; x < n; ++x)
23      for (let u of Object.keys(prefer[x])) {
24        let y = matches[x];
25        let v = matches[u];
26        if (prefer[x][u] < prefer[x][y] && prefer[u][x] < prefer[u][v]) {
27          ++ans;
28          break;
29        }
30      }
31  
32    return ans;
33};

C++ Solution:

1
2cpp
3public:
4  int unhappyFriends(int n, vector<vector<int>>& preferences,
5                     vector<vector<int>>& pairs) {
6    int ans = 0;
7    vector<int> matches(n);
8    vector<unordered_map<int, int>> prefer(n);
9    
10    // Assign pair index using pairs
11    for (const vector<int>& pair : pairs) {
12      const int x = pair[0];
13      const int y = pair[1];
14      matches[x] = y;
15      matches[y] = x;
16    }
17    
18    // Assign preferness index
19    for (int i = 0; i < n; ++i)
20      for (int j = 0; j < n - 1; ++j)
21        prefer[i][preferences[i][j]] = j;
22    
23    // Iterate over all friends
24    for (int x = 0; x < n; ++x)
25      for (const auto& [u, _] : prefer[x]) {
26        const int y = matches[x];
27        const int v = matches[u];
28        if (prefer[x][u] < prefer[x][y] && prefer[u][x] < prefer[u][v]) {
29          ++ans;
30          break;
31        }
32      }
33
34    return ans;
35  }
36};

C# Solution:

1
2csharp
3public class Solution {
4    public int UnhappyFriends(int n, int[][] preferences, int[][] pairs) {
5        var ans = 0;
6        int[] matches = new int[n];
7        int[,] prefer = new int[n, n];
8   
9        // Assign pair index using pairs
10        foreach (var pair in pairs) {
11          var x = pair[0];
12          var y = pair[1];
13          matches[x] = y;
14          matches[y] = x;
15        }
16        
17        // assign preferness index
18        for (var i = 0; i < n; ++i)
19          for (var j = 0; j < n - 1; ++j)
20            prefer[i, preferences[i][j]] = j;
21            
22        // Iterate over all friends
23        for (var x = 0; x < n; ++x)
24          for (var u = 0; u < n - 1; ++u) {
25            var y = matches[x];
26            var v = matches[preferences[x][u]];
27            if (preferences[x][u] != y && 
28                prefer[x, preferences[x][u]] < prefer[x, y] && 
29                prefer[preferences[x][u], x] < prefer[preferences[x][u], v])
30            {
31                ++ans;
32                break;
33            }
34          }
35      return ans;
36    }
37}

In each of the above solutions, we initialize some arrays (or equivalent data structure) to store the matching pairs and specific rankings. We then nested iterate over the preferences and matches to determine if a friend is unhappy based on the stated condition. If all conditions are met, we increment the counter of unhappy friends. The final count is returned.## Testing

You can validate your solution by using this simple test case.

Test Case 1

For the given test case:

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

Your function should return 2.

Complexity analysis

The space complexity is O(n^2) due to the storage of all friends' preferences in an n*n array.

As for the runtime complexity, it is also O(n^2). Even though it seems like it could be O(n^3), but it’s really not. Although there are three nested loops in each function, the innermost loop will run at most (n - 1) times for every friend, thus concluding the total time is O(n^2).

It's vital to note that this approach assumes the value of n (i.e., the number of friends) is relatively small. If n becomes very large, alternate, more efficient algorithms may need to be explored.

These codes are designed to give an accurate number of unhappy friends in the stated friend pairing problem, based on an individual's preference. The solutions are provided in six different languages to cater to different programming preferences.

Remember, all solutions are correct, and they are equivalent in logic, differing only in syntax due to the programming language being used. The problem can have variations, such as having the friends ranked in different orders of preference, and these solutions are flexible to handle those changes.

The important factor is understanding the problem at hand, the data you need to solve it, the expected output, and how to translate this into your preferred programming language. Once you have these, you can solve virtually any problem.