Watch 8 video solutions for Count Unhappy Friends, a medium level problem involving Array, Simulation. This walkthrough by babybear4812 has 4,064 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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).
| 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. |