Skip to main content
Talentd

Count Unhappy Friends - Solution & Explanation

MediumArraySimulation14 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

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.

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.

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.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n^2) due to nested loop iterating over preferences.
Space Complexity: O(n^2) due to the storage of preference mappings.

Try this approach in the editor →

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.

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(n^2) due to preference search in listings.
Space Complexity: O(n) because of the simple partner storage.

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Mapping Preferences

Time Complexity: O(n^2) due to nested loop iterating over preferences.
Space Complexity: O(n^2) due to the storage of preference mappings.

Direct Pair Comparison

Time Complexity: O(n^2) due to preference search in listings.
Space Complexity: O(n) because of the simple partner storage.

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Pair ComparisonO(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.

Video Solution

LeetCode Solutions 1583. Count Unhappy Friends • Abrar Sher • 1,617 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Count Unhappy Friends with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays