Count Unhappy Friends

Med

#1456Time: O(n^3). The outer loop runs `n` times for each person `x`. The inner loop runs `n` times for each potential person `u`. Inside the inner loop, we perform linear scans on preference lists (`preferences[x]` and `preferences[u]`) to find ranks, each taking O(n) time. This results in a total time complexity of O(n * n * n) = O(n^3).Space: O(n). We use an array `pairedWith` of size `n` to store the pairings.

Data structures

Array

Prompt

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] = [x_i, y_i] denotes x_i is paired with y_i and y_i is paired with x_i.

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
x_i != y_i
0 <= x_i, y_i <= n - 1
Each person is contained in exactly one pair.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem definition into code without much optimization. We iterate through each person x and check if they are unhappy. To do this, we iterate through every other person u and check if the two conditions for unhappiness are met.

The conditions are:

x prefers u over their current partner y.
u prefers x over their current partner v.

To check these preferences, we need to find the positions of the friends in the preference lists. Since the preference lists are sorted by preference, a smaller index means a higher preference. We can find these positions by linearly scanning the respective preference lists.

Algorithm

Create an array pairedWith of size n. Iterate through the pairs list. For each pair [p1, p2], set pairedWith[p1] = p2 and pairedWith[p2] = p1.
Initialize unhappyCount = 0.
Loop for x from 0 to n-1:
- Let y = pairedWith[x].
- Initialize a flag is_x_unhappy = false.
- Loop for u from 0 to n-1:
  - If u == x, continue.
  - Let v = pairedWith[u].
  - To check if x prefers u over y:
    - Find rank_u_for_x and rank_y_for_x by iterating through preferences[x].
  - To check if u prefers x over v:
    - Find rank_x_for_u and rank_v_for_u by iterating through preferences[u].
  - If rank_u_for_x < rank_y_for_x AND rank_x_for_u < rank_v_for_u:
    - Set is_x_unhappy = true.
    - Break the inner loop (over u).
- If is_x_unhappy is true, increment unhappyCount.
Return unhappyCount.

Walkthrough

First, we need an easy way to find out who is paired with whom. We can pre-process the pairs list into an array, let's call it pairedWith, where pairedWith[i] gives the partner of person i. This takes O(n) time.

Then, the main logic proceeds as follows:

Initialize a counter for unhappy friends, unhappyCount, to 0.
Iterate through each person x from 0 to n-1.
For each x, find their partner y = pairedWith[x].
To determine if x is unhappy, we check against every other person u.
For each potential u, find their partner v = pairedWith[u].
Now, check the two unhappiness conditions: a. x prefers u over y: We scan preferences[x] to find the index (rank) of u and y. If rank_of_u < rank_of_y, this condition is met. This scan takes O(n) time. b. u prefers x over v: Similarly, we scan preferences[u] to find the rank of x and v. If rank_of_x < rank_of_v, this condition is met. This scan also takes O(n) time.
If both conditions are true for any u, we've established that x is unhappy. We increment unhappyCount and can immediately stop checking other u's for the current x (by breaking the inner loop) and move to the next person.

The total number of unhappy friends is the final value of unhappyCount.

1class Solution {2    private int getRank(int[] preferenceList, int person) {3        for (int i = 0; i < preferenceList.length; i++) {4            if (preferenceList[i] == person) {5                return i;6            }7        }8        return -1; // Should not happen9    }10 11    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {12        int[] pairedWith = new int[n];13        for (int[] pair : pairs) {14            pairedWith[pair[0]] = pair[1];15            pairedWith[pair[1]] = pair[0];16        }17 18        int unhappyCount = 0;19        for (int x = 0; x < n; x++) {20            int y = pairedWith[x];21            int yRankForX = getRank(preferences[x], y);22 23            boolean foundCauseForUnhappiness = false;24            for (int u = 0; u < n; u++) {25                if (x == u) continue;26 27                int uRankForX = getRank(preferences[x], u);28 29                if (uRankForX < yRankForX) {30                    // x prefers u over y. Now check if u prefers x over its partner.31                    int v = pairedWith[u];32                    int xRankForU = getRank(preferences[u], x);33                    int vRankForU = getRank(preferences[u], v);34 35                    if (xRankForU < vRankForU) {36                        foundCauseForUnhappiness = true;37                        break;38                    }39                }40            }41            if (foundCauseForUnhappiness) {42                unhappyCount++;43            }44        }45        return unhappyCount;46    }47}

Complexity

Time

O(n^3). The outer loop runs `n` times for each person `x`. The inner loop runs `n` times for each potential person `u`. Inside the inner loop, we perform linear scans on preference lists (`preferences[x]` and `preferences[u]`) to find ranks, each taking O(n) time. This results in a total time complexity of O(n * n * n) = O(n^3).

Space

O(n). We use an array `pairedWith` of size `n` to store the pairings.

Trade-offs

Pros

Simple to understand and implement as it directly follows the problem statement.
Low auxiliary space complexity.

Cons

High time complexity, which might be too slow for larger values of n. For n = 500, n^3 is 125,000,000, which could lead to a 'Time Limit Exceeded' error on some platforms.

Solutions

Solution

1class Solution {2public3  int unhappyFriends(int n, int[][] preferences, int[][] pairs) {4    int[][] d = new int[n][n];5    for (int i = 0; i < n; ++i) {6      for (int j = 0; j < n - 1; ++j) {7        d[i][preferences[i][j]] = j;8      }9    }10    int[] p = new int[n];11    for (var e : pairs) {12      int x = e[0], y = e[1];13      p[x] = y;14      p[y] = x;15    }16    int ans = 0;17    for (int x = 0; x < n; ++x) {18      int y = p[x];19      int find = 0;20      for (int i = 0; i < d[x][y]; ++i) {21        int u = preferences[x][i];22        if (d[u][x] < d[u][p[u]]) {23          find = 1;24          break;25        }26      }27      ans += find;28    }29    return ans;30  }31}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem