# Count Unhappy Friends
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/count-unhappy-friends)
Canonical: https://scaleengineer.com/dsa/problems/count-unhappy-friends
**Data structures:** Array
---
## Problem
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.

# Approaches
## Brute-Force Approach
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:
1. `x` prefers `u` over their current partner `y`.
2. `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.
**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.
**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.
### Explanation
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:
1. Initialize a counter for unhappy friends, `unhappyCount`, to 0.
2. Iterate through each person `x` from `0` to `n-1`.
3. For each `x`, find their partner `y = pairedWith[x]`.
4. To determine if `x` is unhappy, we check against every other person `u`.
5. For each potential `u`, find their partner `v = pairedWith[u]`.
6. 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.
7. 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`.

```java
class Solution {
    private int getRank(int[] preferenceList, int person) {
        for (int i = 0; i < preferenceList.length; i++) {
            if (preferenceList[i] == person) {
                return i;
            }
        }
        return -1; // Should not happen
    }

    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        int[] pairedWith = new int[n];
        for (int[] pair : pairs) {
            pairedWith[pair[0]] = pair[1];
            pairedWith[pair[1]] = pair[0];
        }

        int unhappyCount = 0;
        for (int x = 0; x < n; x++) {
            int y = pairedWith[x];
            int yRankForX = getRank(preferences[x], y);

            boolean foundCauseForUnhappiness = false;
            for (int u = 0; u < n; u++) {
                if (x == u) continue;

                int uRankForX = getRank(preferences[x], u);

                if (uRankForX < yRankForX) {
                    // x prefers u over y. Now check if u prefers x over its partner.
                    int v = pairedWith[u];
                    int xRankForU = getRank(preferences[u], x);
                    int vRankForU = getRank(preferences[u], v);

                    if (xRankForU < vRankForU) {
                        foundCauseForUnhappiness = true;
                        break;
                    }
                }
            }
            if (foundCauseForUnhappiness) {
                unhappyCount++;
            }
        }
        return unhappyCount;
    }
}
```
### 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`.

## Optimized Approach using a Rank Matrix
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.
**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).
**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.
### Explanation
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.
1. Initialize `unhappyCount = 0`.
2. Iterate through each person `x` from `0` to `n-1`.
3. Find their partner `y = pairedWith[x]`.
4. 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.
5. So, we iterate through `x`'s preference list, `preferences[x]`. Let the person at the current position be `u`.
6. 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.
7. 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.
8. 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.

```java
class Solution {
    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        // Step 1: Pre-computation
        // Store who is paired with whom for O(1) lookup.
        int[] pairedWith = new int[n];
        for (int[] pair : pairs) {
            pairedWith[pair[0]] = pair[1];
            pairedWith[pair[1]] = pair[0];
        }

        // Store preference ranks for O(1) lookup.
        // ranks[i][j] = rank of person j in person i's preference list.
        int[][] ranks = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - 1; j++) {
                int friend = preferences[i][j];
                ranks[i][friend] = j;
            }
        }

        // Step 2: Count unhappy friends
        int unhappyCount = 0;
        for (int x = 0; x < n; x++) {
            int y = pairedWith[x];
            int rankOfY = ranks[x][y];

            // Iterate through people x prefers more than y
            for (int i = 0; i < rankOfY; i++) {
                int u = preferences[x][i];
                int v = pairedWith[u];

                // Check if u also prefers x over their partner v
                if (ranks[u][x] < ranks[u][v]) {
                    unhappyCount++;
                    // Found a reason for x to be unhappy, move to the next person.
                    break;
                }
            }
        }

        return unhappyCount;
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
    int[][] d = new int[n][n];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n - 1; ++j) {
        d[i][preferences[i][j]] = j;
      }
    }
    int[] p = new int[n];
    for (var e : pairs) {
      int x = e[0], y = e[1];
      p[x] = y;
      p[y] = x;
    }
    int ans = 0;
    for (int x = 0; x < n; ++x) {
      int y = p[x];
      int find = 0;
      for (int i = 0; i < d[x][y]; ++i) {
        int u = preferences[x][i];
        if (d[u][x] < d[u][p[u]]) {
          find = 1;
          break;
        }
      }
      ans += find;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int unhappyFriends(int n, vector<vector<int>> &preferences,
                     vector<vector<int>> &pairs) {
    int d[n][n];
    int p[n];
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n - 1; ++j) {
        d[i][preferences[i][j]] = j;
      }
    }
    for (auto &e : pairs) {
      int x = e[0], y = e[1];
      p[x] = y;
      p[y] = x;
    }
    int ans = 0;
    for (int x = 0; x < n; ++x) {
      int y = p[x];
      int find = 0;
      for (int i = 0; i < d[x][y]; ++i) {
        int u = preferences[x][i];
        if (d[u][x] < d[u][p[u]]) {
          find = 1;
          break;
        }
      }
      ans += find;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```