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.

The bottleneck in the brute-force approach is repeatedly scanning the preference lists to determine the rank of a friend. This operation takes O(n) time and is performed inside nested loops, leading to an overall O(n^3) complexity.

We can significantly optimize this by pre-computing the ranks. We can use a 2D array, ranks, where ranks[i][j] stores the preference rank of person j for person i. A lower rank value means a higher preference. For example, if preferences[i] = [2, 1, 0], then ranks[i][2] = 0, ranks[i][1] = 1, and ranks[i][0] = 2.

After building this ranks matrix, checking if i prefers j over k becomes an O(1) lookup: ranks[i][j] < ranks[i][k]. This pre-computation step takes O(n^2) time, but it allows the main logic to run much faster.

Algorithm

Create an array pairedWith of size n. Iterate through pairs to populate it.
Create a 2D array ranks of size n x n.
Loop for i from 0 to n-1:
- Loop for j from 0 to n-2:
  - Let friend = preferences[i][j].
  - Set ranks[i][friend] = j.
Initialize unhappyCount = 0.
Loop for x from 0 to n-1:
- Let y = pairedWith[x].
- Let rankOfY = ranks[x][y].
- Loop for i from 0 to rankOfY - 1:
  - Let u = preferences[x][i].
  - Let v = pairedWith[u].
  - If ranks[u][x] < ranks[u][v]:
    - Increment unhappyCount.
    - Break the inner loop (over i).
Return unhappyCount.

Walkthrough

The improved algorithm consists of two main phases: pre-computation and counting.

1. Pre-computation:

First, just like in the brute-force method, we create a pairedWith array of size n to store the partner for each person. This takes O(n) time.
Next, we create the ranks matrix of size n x n. We iterate through each person i from 0 to n-1. For each person, we iterate through their preferences[i] list. If preferences[i][j] = k, it means person i's j-th preference is person k. So, we set ranks[i][k] = j. This process fills the entire ranks matrix and takes O(n^2) time.

2. Counting Unhappy Friends: With the pairedWith and ranks data structures ready, we can efficiently count the unhappy friends.

Initialize unhappyCount = 0.
Iterate through each person x from 0 to n-1.
Find their partner y = pairedWith[x].
Now, we need to find if there's any person u that makes x unhappy. A person u makes x unhappy if x prefers u over y. These are exactly the people who appear before y in x's preference list.
So, we iterate through x's preference list, preferences[x]. Let the person at the current position be u.
If we encounter y (i.e., u == y), we can stop. Any person appearing after y in the list is less preferred, so they cannot make x unhappy.
For each u that is more preferred than y, we check the second condition: does u prefer x over their own partner v?
- Find u's partner: v = pairedWith[u].
- Check the preference using our ranks matrix: ranks[u][x] < ranks[u][v]. This is an O(1) operation.
If this condition is true, we have found a reason for x to be unhappy. We increment unhappyCount, and we can break out of the inner loop (iterating through x's preferences) and move to the next person.

This refined logic avoids the O(n^3) complexity by replacing the O(n) preference check with an O(1) lookup, at the cost of O(n^2) space and pre-computation time.

1class Solution {2    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {3        // Step 1: Pre-computation4        // Store who is paired with whom for O(1) lookup.5        int[] pairedWith = new int[n];6        for (int[] pair : pairs) {7            pairedWith[pair[0]] = pair[1];8            pairedWith[pair[1]] = pair[0];9        }10 11        // Store preference ranks for O(1) lookup.12        // ranks[i][j] = rank of person j in person i's preference list.13        int[][] ranks = new int[n][n];14        for (int i = 0; i < n; i++) {15            for (int j = 0; j < n - 1; j++) {16                int friend = preferences[i][j];17                ranks[i][friend] = j;18            }19        }20 21        // Step 2: Count unhappy friends22        int unhappyCount = 0;23        for (int x = 0; x < n; x++) {24            int y = pairedWith[x];25            int rankOfY = ranks[x][y];26 27            // Iterate through people x prefers more than y28            for (int i = 0; i < rankOfY; i++) {29                int u = preferences[x][i];30                int v = pairedWith[u];31 32                // Check if u also prefers x over their partner v33                if (ranks[u][x] < ranks[u][v]) {34                    unhappyCount++;35                    // Found a reason for x to be unhappy, move to the next person.36                    break;37                }38            }39        }40 41        return unhappyCount;42    }43}

Complexity

Time

O(n^2). * Building `pairedWith` takes O(n). * Building the `ranks` matrix takes O(n^2) because we iterate through `n` preference lists, each of size `n-1`. * The final counting loop iterates through each person `x` (n times). The inner loop iterates through `x`'s more preferred friends. In the worst case, a partner `y` can have the lowest rank (`n-2`), so the inner loop runs up to `n-1` times. This gives a complexity of O(n^2) for counting. * The total time complexity is dominated by the O(n^2) steps, so it is O(n^2).

Space

O(n^2). * The `pairedWith` array takes O(n) space. * The `ranks` matrix is the main contributor to space, requiring O(n^2) space. * Total space complexity is O(n^2).

Trade-offs

Pros

Much more efficient than the brute-force approach, with a time complexity that is well within limits for the given constraints.
The logic is clean and directly models the problem after the pre-computation step.

Cons

Requires significant auxiliary space (O(n^2)) for the ranks matrix, which could be an issue if n were much larger.

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}

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

1class Solution:2    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int: d = [{p: i for i, p in enumerate(v)} for v in preferences] p = {} for x, y in pairs: p[x] = y p[y] = x ans = 0 for x in range(n): y = p[x] ans += any(d[u][x] < d[u][p[u]] for u in preferences[x][: d[x][y]]) return ans

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