1583. Count Unhappy Friends LeetCode Solution

In this guide, you will get 1583. Count Unhappy Friends LeetCode Solution with the best time and space complexity. The solution to Count Unhappy Friends problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Unhappy Friends solution in C++
Count Unhappy Friends solution in Java
Count Unhappy Friends solution in Python
Additional Resources

1583. Count Unhappy Friends LeetCode Solution image

Problem Statement of Count Unhappy Friends

You are given a list of preferences for n friends, where n is always even.
For each person i, preferences[i] contains a list of friends sorted in the order of preference. In other words, a friend earlier in the list is more preferred than a friend later in the list. Friends in each list are denoted by integers from 0 to n-1.
All the friends are divided into pairs. The pairings are given in a list pairs, where pairs[i] = [xi, yi] denotes xi is paired with yi and yi is paired with xi.
However, this pairing may cause some of the friends to be unhappy. A friend x is unhappy if x is paired with y and there exists a friend u who is paired with v but:

x prefers u over y, and
u prefers x over v.

Return the number of unhappy friends.

Example 1:

Input: n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]]
Output: 2
Explanation:
Friend 1 is unhappy because:
– 1 is paired with 0 but prefers 3 over 0, and
– 3 prefers 1 over 2.
Friend 3 is unhappy because:
– 3 is paired with 2 but prefers 1 over 2, and
– 1 prefers 3 over 0.
Friends 0 and 2 are happy.

Example 2:

Input: n = 2, preferences = [[1], [0]], pairs = [[1, 0]]
Output: 0
Explanation: Both friends 0 and 1 are happy.

Example 3:

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

Constraints:

2 <= n <= 500
n is even.
preferences.length == n
preferences[i].length == n – 1
0 <= preferences[i][j] <= n – 1
preferences[i] does not contain i.
All values in preferences[i] are unique.
pairs.length == n/2
pairs[i].length == 2
xi != yi
0 <= xi, yi <= n – 1
Each person is contained in exactly one pair.

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(n^2)

1583. Count Unhappy Friends LeetCode Solution in C++

class Solution {
 public:
  int unhappyFriends(int n, vector<vector<int>>& preferences,
                     vector<vector<int>>& pairs) {
    int ans = 0;
    vector<int> matches(n);
    vector<unordered_map<int, int>> prefer(n);

    for (const vector<int>& pair : pairs) {
      const int x = pair[0];
      const int y = pair[1];
      matches[x] = y;
      matches[y] = x;
    }

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n - 1; ++j)
        prefer[i][preferences[i][j]] = j;

    for (int x = 0; x < n; ++x)
      for (const auto& [u, _] : prefer[x]) {
        const int y = matches[x];
        const int v = matches[u];
        if (prefer[x][u] < prefer[x][y] && prefer[u][x] < prefer[u][v]) {
          ++ans;
          break;
        }
      }

    return ans;
  }
};
/* code provided by PROGIEZ */

1583. Count Unhappy Friends LeetCode Solution in Java

class Solution {
  public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
    int ans = 0;
    int[] matches = new int[n];
    Map<Integer, Integer>[] prefer = new Map[n];

    for (int[] pair : pairs) {
      final int x = pair[0];
      final int y = pair[1];
      matches[x] = y;
      matches[y] = x;
    }

    for (int i = 0; i < n; ++i)
      prefer[i] = new HashMap<>();

    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n - 1; ++j)
        prefer[i].put(preferences[i][j], j);

    for (int x = 0; x < n; ++x)
      for (final int u : preferences[x]) {
        final int y = matches[x];
        final int v = matches[u];
        if (prefer[x].get(u) < prefer[x].get(y) && prefer[u].get(x) < prefer[u].get(v)) {
          ++ans;
          break;
        }
      }

    return ans;
  }
}
// code provided by PROGIEZ

1583. Count Unhappy Friends LeetCode Solution in Python

class Solution:
  def unhappyFriends(
      self,
      n: int,
      preferences: list[list[int]],
      pairs: list[list[int]],
  ) -> int:
    ans = 0
    matches = [0] * n
    prefer = [{} for _ in range(n)]

    for x, y in pairs:
      matches[x] = y
      matches[y] = x

    for i in range(n):
      for j in range(n - 1):
        prefer[i][preferences[i][j]] = j

    for x in range(n):
      for u in prefer[x].keys():
        y = matches[x]
        v = matches[u]
        if prefer[x][u] < prefer[x][y] and prefer[u][x] < prefer[u][v]:
          ans += 1
          break

    return ans
 # code by PROGIEZ