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, andu 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 <= 500n is even.preferences.length == npreferences[i].length == n - 10 <= preferences[i][j] <= n - 1preferences[i] does not contain i.preferences[i] are unique.pairs.length == n/2pairs[i].length == 2xi != yi0 <= xi, yi <= n - 1Problem Overview: You are given n friends, each with a ranked list of preferred friends, and a list of pairs representing current matches. A friend becomes unhappy if they prefer another friend over their current partner and that friend also prefers them over their own partner. The goal is to count how many friends are unhappy.
Approach 1: Direct Pair Comparison (O(n^3) time, O(1) space)
This method simulates the definition of unhappiness directly. For each friend x, find their current partner y. Iterate through everyone u that x prefers more than y. For each such candidate, locate u's partner v and check if u prefers x over v. If both conditions hold, x is unhappy. Because preference lookups require scanning lists and each friend may check multiple others, the nested checks push the total complexity to O(n^3). This approach is easy to reason about and mirrors the problem statement, but becomes inefficient as n grows.
Approach 2: Mapping Preferences (O(n^2) time, O(n^2) space)
The optimized solution precomputes a ranking matrix where rank[a][b] represents how much friend a prefers friend b. Lower values indicate higher preference. This allows constant-time preference comparison instead of scanning lists. Build a map from each friend to their partner, then iterate through each pair (x, y). For every friend u that x prefers over y, check in O(1) time whether u prefers x over their own partner v using the rank matrix. The preprocessing step costs O(n^2), and each comparison is constant time, reducing the total complexity to O(n^2). This technique relies heavily on indexed lookups and works well with problems involving preference ranking or repeated comparisons in Array and Simulation scenarios.
Recommended for interviews: The mapping-based approach is what interviewers usually expect. Starting with the direct simulation shows you understand the unhappy condition clearly. Converting preference lists into a rank lookup table demonstrates optimization thinking and reduces repeated scans, bringing the runtime down to O(n^2).
Create a preference rank map for quick lookup of preference rankings. Use this mapping to check if a friend x is unhappy by iterating over all their preferred friends u appearing before their current pair. If the friend u also prefers x over their current pair v, count x as unhappy.
The function first creates a mapping (prefer_map) that associates each friend with their rank in the preference list for quick lookup. Then, it establishes current partnerships in a partners array. It iterates through each friend, checking their preference list against their current partner. If a preferred friend u ranks the current friend x higher than their own partner, x is deemed unhappy. The function keeps count of unhappy friends and finally returns this count.
Time Complexity: O(n^2) due to nested loop iterating over preferences.
Space Complexity: O(n^2) due to the storage of preference mappings.
Directly compare each pair with other pairs to determine if there's any mutual unhappiness based on preferences. This approach involves checking each pairing's mutual preference satisfaction without creating extra data structures.
The method creates a partners array to store everyone's current partner. It then iterates over each person, checking if they prefer anyone over their current partner who also prefers them back more than their current partner. The preference check is performed using Java's List method to find the index. If mutual preference exists, the unhappy counter is incremented.
Java
JavaScript
Time Complexity: O(n^2) due to preference search in listings.
Space Complexity: O(n) because of the simple partner storage.
We use an array d to record the closeness between each pair of friends, where d[i][j] represents the closeness of friend i to friend j (the smaller the value, the closer they are). Additionally, we use an array p to record the paired friend for each friend.
We enumerate each friend x. For x's paired friend y, we find the closeness d[x][y] of x to y. Then, we enumerate other friends u who are closer than d[x][y]. If there exists a friend u such that the closeness d[u][x] of u to x is higher than d[u][y], then x is an unhappy friend, and we increment the result by one.
After the enumeration, we obtain the number of unhappy friends.
The time complexity is O(n^2), and the space complexity is O(n^2). Here, n is the number of friends.
| Approach | Complexity |
|---|---|
| Mapping Preferences | Time Complexity: O(n^2) due to nested loop iterating over preferences. |
| Direct Pair Comparison | Time Complexity: O(n^2) due to preference search in listings. |
| Enumeration | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Pair Comparison | O(n^3) | O(1) | When implementing a straightforward simulation of the problem definition or during initial brute-force reasoning. |
| Mapping Preferences (Rank Matrix) | O(n^2) | O(n^2) | Preferred approach for interviews and production solutions where fast preference comparisons are required. |
COUNT UNHAPPY FRIENDS (Leetcode) - Code & Whiteboard • babybear4812 • 4,064 views views
Watch 7 more video solutions →Practice Count Unhappy Friends with our built-in code editor and test cases.
Practice on FleetCode