Skip to content

1583. Count Unhappy Friends 👎

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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