Count Unhappy Friends - Practice Coding Problems

Count Unhappy Friends - Problem

Array Simulation Medium

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.

Input & Output

Example 1 — Basic Unhappiness

$ Input: preferences = [[1,2,3],[3,2,0],[3,1,0],[1,2,0]], pairs = [[0,1],[2,3]]

› Output: 2

💡 Note: Person 0 is paired with 1 but prefers 2, and person 2 prefers 0 over their partner 3. Similarly, person 2 is unhappy for the same mutual preference. So 2 people are unhappy.

Example 2 — Everyone Happy

$ Input: preferences = [[1,3,2],[2,3,0],[1,3,0],[0,2,1]], pairs = [[0,1],[2,3]]

› Output: 0

💡 Note: No one can find someone they prefer more who also prefers them back over their current partner. Everyone is happy with their current pairing.

Example 3 — Multiple Pairs

$ Input: preferences = [[1,3,2,5,4],[2,3,0,4,5],[3,0,1,4,5],[2,1,4,0,5],[2,1,0,3,5],[3,1,0,2,4]], pairs = [[0,1],[2,3],[4,5]]

› Output: 4

💡 Note: With 6 people in 3 pairs, multiple people find mutually preferred alternatives to their current partners, resulting in 4 unhappy friends.

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
0 ≤ xi, yi ≤ n - 1
xi ≠ yi
All pairs contain different people

Visualization

Tap to expand

Understanding the Visualization

Input

Preference lists for each person and current pair assignments

Process

Check if anyone prefers someone else who also prefers them back

Output

Count of people who are unhappy with current pairing

Key Takeaway

🎯 Key Insight: A person is unhappy only when there exists mutual preference - they prefer someone who also prefers them back over current partners

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is that a person is unhappy only when they can find someone who mutually prefers them over their current partners. The optimal approach uses preference ranking maps to enable O(1) preference lookups, reducing complexity from O(n³) to O(n²). Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n³)	O(n)	Check every friend against every other friend to see if they form a mutually preferred pair
Optimized with Preference Maps	O(n²)	O(n²)	Pre-build preference ranking maps to avoid linear searches for each comparison

Brute Force Simulation — Algorithm Steps

Step 1: Create a mapping from each person to their current partner
Step 2: For each person x, check every other person u to see if x prefers u over their partner and u prefers x over their partner
Step 3: Count how many people are unhappy

Visualization

Tap to expand

Step-by-Step Walkthrough

Current Pairings

Map everyone to their current partner

Check Alternatives

For each person, check if they prefer someone else who also prefers them

Count Unhappy

Count people who found a mutually preferred alternative

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int preferences[][4], int n, int pairs[][2], int numPairs) {
    int partner[n];
    
    // Map each person to their partner
    for (int i = 0; i < numPairs; i++) {
        partner[pairs[i][0]] = pairs[i][1];
        partner[pairs[i][1]] = pairs[i][0];
    }
    
    int unhappyCount = 0;
    
    // Check each person
    for (int x = 0; x < n; x++) {
        int y = partner[x];
        
        // Check if x is unhappy
        for (int u = 0; u < n; u++) {
            if (u == x || u == y) continue;
            
            int v = partner[u];
            
            // Find preference indices
            int uIdx = -1, yIdx = -1;
            for (int i = 0; i < n-1; i++) {
                if (preferences[x][i] == u) uIdx = i;
                if (preferences[x][i] == y) yIdx = i;
            }
            
            int xIdx = -1, vIdx = -1;
            for (int i = 0; i < n-1; i++) {
                if (preferences[u][i] == x) xIdx = i;
                if (preferences[u][i] == v) vIdx = i;
            }
            
            if (uIdx < yIdx && xIdx < vIdx) {
                unhappyCount++;
                break;
            }
        }
    }
    
    return unhappyCount;
}

int main() {
    // Simplified for demo
    int preferences[4][4] = {{1, 2, 3}, {3, 2, 0}, {3, 1, 0}, {1, 2, 0}};
    int pairs[2][2] = {{0, 1}, {2, 3}};
    
    int result = solution(preferences, 4, pairs, 2);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of n people, we check n other people, and each preference check takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Hash map to store partner mappings uses O(n) space

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler