Count Unhappy Friends solution and explanation
Google
8 more videos on this problem
LeetCode Solutions 1583. Count Unhappy FriendsAbrar Sher · 8:49 · 1K views
1583. Count Unhappy Friends (Leetcode Medium)Programming Live with Larry · 15:21 · 1K views
1583 Count Unhappy Friends leetcode (java)Sloppy Guy · 19:37 · 563 views
LeetCode 1583. Count Unhappy Friends | JSer - JavaScript & AlgorithmJSer · 16:18 · 458 views
1583. Count Unhappy FriendsMuerde un zombie · 18:17 · 156 views
Count Unhappy Friends (LeetCode- 1583) | Level - Medium | By Mapping and Rank Matrix OptimizationAi_with_Sara · 6:03 · 56 views
LeetCode 1583: Count Unhappy Friends | Intuition + Optimal Solution Explained (Python)Tech With Hos · 11:07 · 25 views
LeetCode 1583: Count Unhappy FriendsAlitaCode · 28:15 · 7 views
ข้อ 1583. Count Unhappy Friends | LeetCodeThakorn Jareonrat · 8:06 · 1 view
The 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:
xprefersuovery, anduprefersxoverv.
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 <= 500nis even.preferences.length == npreferences[i].length == n - 10 <= preferences[i][j] <= n - 1preferences[i]does not containi.- All values in
preferences[i]are unique. pairs.length == n/2pairs[i].length == 2xi != yi0 <= xi, yi <= n - 1- Each person is contained in exactly one pair.
Approach overview
Problem 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).
Approach 1: Mapping Preferences
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.
def count_unhappy_friends(n, preferences, pairs):
prefer_map = {i: {f: idx for idx, f in enumerate(pref)} for i, pref in enumerate(preferences)}
partners = [0] * n
unhappy_count = 0
for x, y in pairs:
partners[x] = y
partners[y] = x
for x in range(n):
y = partners[x]
for u in preferences[x]:
if u == y:
break
v = partners[u]
if prefer_map[u][x] < prefer_map[u][v]:
unhappy_count += 1
break
return unhappy_count#include <vector>
#include <unordered_map>
using namespace std;
int countUnhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
unordered_map<int, unordered_map<int, int>> preferMap;
vector<int> partners(n);
int unhappyCount = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n - 1; ++j) {
preferMap[i][preferences[i][j]] = j;
}
}
for (auto& pair : pairs) {
int x = pair[0], y = pair[1];
partners[x] = y;
partners[y] = x;
}
for (int x = 0; x < n; ++x) {
int y = partners[x];
for (int u : preferences[x]) {
if (u == y) break;
int v = partners[u];
if (preferMap[u][x] < preferMap[u][v]) {
unhappyCount++;
break;
}
}
}
return unhappyCount;
}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.
Approach 2: Direct Pair Comparison
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.
import java.util.*;
public class UnhappyFriends {
public int countUnhappyFriends(int n, int[][] preferences, int[][] pairs) {
int[] partners = new int[n];
for (int[] pair : pairs) {
partners[pair[0]] = pair[1];
partners[pair[1]] = pair[0];
}
int unhappyCount = 0;
for (int x = 0; x < n; x++) {
int y = partners[x];
for (int u : preferences[x]) {
if (u == y) break;
int v = partners[u];
List<Integer> preferU = Arrays.asList(preferences[u]);
if (preferU.indexOf(x) < preferU.indexOf(v)) {
unhappyCount++;
break;
}
}
}
return unhappyCount;
}
}function countUnhappyFriends(n, preferences, pairs) {
const partners = Array(n);
for (let [x, y] of pairs) {
partners[x] = y;
partners[y] = x;
}
let unhappyCount = 0;
for (let x = 0; x < n; x++) {
const y = partners[x];
for (const u of preferences[x]) {
if (u === y) break;
const v = partners[u];
if (preferences[u].indexOf(x) < preferences[u].indexOf(v)) {
unhappyCount++;
break;
}
}
}
return unhappyCount;
}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.
Time Complexity: O(n^2) due to preference search in listings.
Space Complexity: O(n) because of the simple partner storage.
Approach 3: Enumeration
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.
function unhappyFriends(n: number, preferences: number[][], pairs: number[][]): number {
const d: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n - 1; ++j) {
d[i][preferences[i][j]] = j;
}
}
const p: number[] = Array(n).fill(0);
for (const [x, y] of pairs) {
p[x] = y;
p[y] = x;
}
let ans = 0;
for (let x = 0; x < n; ++x) {
const y = p[x];
for (let i = 0; i < d[x][y]; ++i) {
const u = preferences[x][i];
const v = p[u];
if (d[u][x] < d[u][v]) {
++ans;
break;
}
}
}
return ans;
}func unhappyFriends(n int, preferences [][]int, pairs [][]int) (ans int) {
d := make([][]int, n)
for i := range d {
d[i] = make([]int, n)
}
for i := 0; i < n; i++ {
for j := 0; j < n-1; j++ {
d[i][preferences[i][j]] = j
}
}
p := make([]int, n)
for _, e := range pairs {
x, y := e[0], e[1]
p[x] = y
p[y] = x
}
for x := 0; x < n; x++ {
y := p[x]
for i := 0; i < d[x][y]; i++ {
u := preferences[x][i]
v := p[u]
if d[u][x] < d[u][v] {
ans++
break
}
}
}
return
}impl Solution {
pub fn unhappy_friends(n: i32, preferences: Vec<Vec<i32>>, pairs: Vec<Vec<i32>>) -> i32 {
let n = n as usize;
let mut d = vec![vec![0usize; n]; n];
for i in 0..n {
for j in 0..(n - 1) {
let friend = preferences[i][j] as usize;
d[i][friend] = j;
}
}
let mut p = vec![0usize; n];
for e in pairs {
let x = e[0] as usize;
let y = e[1] as usize;
p[x] = y;
p[y] = x;
}
let mut ans = 0;
for x in 0..n {
let y = p[x];
for i in 0..d[x][y] {
let u = preferences[x][i] as usize;
let v = p[u];
if d[u][x] < d[u][v] {
ans += 1;
break;
}
}
}
ans
}
}Complexity comparison
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Count Unhappy Friends easy or hard?
Count Unhappy Friends is rated Medium difficulty. The logic is straightforward once the definition of an unhappy friend is clear, but optimizing repeated preference checks using a ranking matrix requires careful thinking.
Count Unhappy Friends Python/Java solution
Python solutions typically build a rank matrix using a list of lists and a partner array for pair lookup. Java implementations use 2D arrays for ranking and iterate through preference lists to detect unhappy conditions with O(n^2) complexity.
How to solve Count Unhappy Friends in O(n^2)?
Create a 2D rank array where rank[a][b] represents how much friend a prefers friend b. Store each person's partner from the given pairs. Then check only the friends a person prefers more than their partner and verify the reverse preference using constant-time rank lookups.
What is the best approach for Count Unhappy Friends?
The best approach is building a preference ranking matrix and mapping each friend to their current partner. This allows constant-time preference comparisons and reduces repeated list scans. The overall complexity becomes O(n^2) time with O(n^2) extra space.
Is Count Unhappy Friends asked at Google/Amazon/Meta?
Problems involving preference rankings, pair validation, and simulation patterns appear in interviews at companies like Amazon, Google, and Meta. This problem specifically tests careful condition checking and efficient lookup optimization.
What data structure is used in Count Unhappy Friends?
The optimized solution uses arrays to store preference rankings (a rank matrix) and a mapping from each friend to their assigned partner. These structures allow O(1) preference comparisons during the simulation.
What is the time complexity of Count Unhappy Friends?
The optimal solution runs in O(n^2) time by precomputing a ranking matrix for preference comparisons. A naive simulation that scans preference lists repeatedly can degrade to O(n^3) time.