Code Implementation

class Solution:
    def unhappyFriends(self, n, preferences, pairs):
        # Build a ranking matrix for quick lookup
        rank = [[0]*n for _ in range(n)]
        for i in range(n):
            for j, friend in enumerate(preferences[i]):
                rank[i][friend] = j

        # Pair mapping: person -> their pair
        pair_map = {}
        for x, y in pairs:
            pair_map[x] = y
            pair_map[y] = x

        unhappy = set()
        for x in range(n):
            y = pair_map[x]
            # All people x prefers over y
            for u in preferences[x]:
                if u == y:
                    break
                v = pair_map[u]
                # If u prefers x over their own pair v
                if rank[u][x] < rank[u][v]:
                    unhappy.add(x)
                    break
        return len(unhappy)
    

class Solution {
public:
    int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
        vector<vector<int>> rank(n, vector<int>(n));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n - 1; ++j)
                rank[i][preferences[i][j]] = j;

        vector<int> pair_map(n);
        for (auto& p : pairs) {
            pair_map[p[0]] = p[1];
            pair_map[p[1]] = p[0];
        }

        int unhappy = 0;
        for (int x = 0; x < n; ++x) {
            int y = pair_map[x];
            for (int i = 0; preferences[x][i] != y; ++i) {
                int u = preferences[x][i];
                int v = pair_map[u];
                if (rank[u][x] < rank[u][v]) {
                    ++unhappy;
                    break;
                }
            }
        }
        return unhappy;
    }
};
    

class Solution {
    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        int[][] rank = new int[n][n];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n - 1; ++j)
                rank[i][preferences[i][j]] = j;

        int[] pair_map = new int[n];
        for (int[] p : pairs) {
            pair_map[p[0]] = p[1];
            pair_map[p[1]] = p[0];
        }

        int unhappy = 0;
        for (int x = 0; x < n; ++x) {
            int y = pair_map[x];
            for (int i = 0; preferences[x][i] != y; ++i) {
                int u = preferences[x][i];
                int v = pair_map[u];
                if (rank[u][x] < rank[u][v]) {
                    unhappy++;
                    break;
                }
            }
        }
        return unhappy;
    }
}
    

var unhappyFriends = function(n, preferences, pairs) {
    const rank = Array.from({length: n}, () => Array(n).fill(0));
    for (let i = 0; i < n; ++i)
        for (let j = 0; j < n - 1; ++j)
            rank[i][preferences[i][j]] = j;

    const pair_map = Array(n);
    for (const [x, y] of pairs) {
        pair_map[x] = y;
        pair_map[y] = x;
    }

    let unhappy = new Set();
    for (let x = 0; x < n; ++x) {
        let y = pair_map[x];
        for (const u of preferences[x]) {
            if (u === y) break;
            let v = pair_map[u];
            if (rank[u][x] < rank[u][v]) {
                unhappy.add(x);
                break;
            }
        }
    }
    return unhappy.size;
};
    

Problem Description

The "Count Unhappy Friends" problem involves a group of n people, each with a list of preferences ranking all other people. These people are paired up into n/2 pairs. A person x is considered unhappy if there exists another person u such that:

• x prefers u over their current pair y, and
• u prefers x over their own pair v.

• Each person is paired with exactly one other person.
• Each person's preference list is a permutation of all other people.
• Each pair is unique and people are not reused.
• There is always a valid pairing.

Inputs:

• n: Number of people (even integer).
• preferences: List of lists, where preferences[i] is the list of people ranked by person i.
• pairs: List of pairs, where each pair is a list of two people.

Thought Process

The problem is about identifying people who are "unhappy" with their assigned pair based on mutual preferences. At first glance, it may seem like we need to check every possible pair of people to see if the unhappiness condition is met, which could be time-consuming for larger groups.

The brute-force approach would involve, for each person, checking every other person to see if the conditions for being unhappy are met. However, since each person only cares about those they prefer over their assigned partner, we can optimize by only considering those people.

To make the checking efficient, we can precompute each person's ranking of others for O(1) lookups and quickly find whether a mutual preference exists. This avoids redundant checks and improves performance.

Solution Approach

• Step 1: Build Ranking Matrix
  For each person, create a quick-lookup table (2D array) where rank[x][u] gives the index of person u in x's preference list. This allows us to check how much x likes u in constant time.
• Step 2: Map Each Person to Their Pair
  Build a mapping from each person to their assigned pair. This helps quickly determine who a person's current partner is.
• Step 3: Iterate Through Each Person
  For each person x, look at everyone they prefer over their assigned partner y. For each such person u, check if u prefers x over their own assigned pair v (using the ranking matrix).
• Step 4: Mark Unhappy Friends
  If both conditions are met, mark x as unhappy. To avoid counting duplicates, use a set or increment a count only once per person.
• Step 5: Return the Count
  At the end, return the number of unhappy friends found.

This approach ensures that each check is efficient, and we only consider relevant people for each person.

Example Walkthrough

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

Step-by-step:

1. Pair Mapping: 0-1, 1-0, 2-3, 3-2
2. Person 0: Paired with 1. Prefers 1 (stop), so no one is preferred over their pair.
   Result: Not unhappy.
3. Person 1: Paired with 0. Prefers 3,2 over 0.
   
   • Check 3: 3 is paired with 2. Does 3 prefer 1 over 2? 3's preferences: [1,2,0] → 1 is before 2, so yes.
     Result: 1 is unhappy.
4. Person 2: Paired with 3. Prefers 3,1,0 over 3: Only 3 is their pair, so no one is preferred over their pair.
   Result: Not unhappy.
5. Person 3: Paired with 2. Prefers 1,2 over 2.
   
   • Check 1: 1 is paired with 0. Does 1 prefer 3 over 0? 1's preferences: [3,2,0] → 3 is before 0, so yes.
     Result: 3 is unhappy.
6. Final Count: 2 unhappy friends (1 and 3).

Time and Space Complexity

• Brute-force Approach:
  For each person, check every other person, and for each, compare their preferences. This is O(n^3) time, since there are O(n^2) pairs and each comparison can take up to O(n).
• Optimized Approach:
  
  • Building the ranking matrix: O(n^2)
  • For each person, only check those they prefer over their pair, which is at most O(n) per person, for a total of O(n^2).
  • All lookups are O(1) due to the ranking matrix.
  Total time complexity: O(n^2)
  Space complexity: O(n^2) for the ranking matrix and pair mapping.

Summary

The key insight in solving the "Count Unhappy Friends" problem is to recognize that each person only needs to check those they prefer over their assigned pair, and that mutual preference can be checked efficiently using a ranking matrix. By mapping each person to their pair and using quick lookups, we reduce the problem from a potentially cubic brute-force approach to a quadratic solution. This efficient design ensures the solution is both fast and easy to understand, making it suitable for larger inputs and demonstrating the power of precomputation and smart data structures.