LeetCode 1583 - Count Unhappy Friends

In this problem, we are given n friends, where n is always even. Every friend ranks all other friends in order of preference. The earlier someone appears in a person's preference list, the more that person is preferred. We are also given a final pairing arrangement.

leetcodemediumarraysimulation

LeetCode Problem 1583

Difficulty: 🟡 Medium
Topics: Array, Simulation

Solution

Problem Understanding

In this problem, we are given n friends, where n is always even. Every friend ranks all other friends in order of preference. The earlier someone appears in a person's preference list, the more that person is preferred.

We are also given a final pairing arrangement. Each person is paired with exactly one other person.

The goal is to determine how many friends are "unhappy" with their assigned partner.

A friend x becomes unhappy if there exists another friend u such that:

  1. x prefers u over their current partner y
  2. u also prefers x over u's current partner v

This definition is important because unhappiness is mutual in nature. It is not enough for x to prefer someone else. That other person must also prefer x over their own assigned partner.

The input consists of:

  • n, the number of friends
  • preferences, where preferences[i] is the ordered list of people that friend i prefers
  • pairs, which contains the final pairing arrangement

The output is a single integer representing the number of unhappy friends.

The constraints tell us several important things:

  • n <= 500, so an O(n^2) solution is perfectly acceptable
  • Every preference list has length n - 1
  • Preferences are unique and complete
  • Every person belongs to exactly one pair

These guarantees simplify the implementation significantly because we never need to handle invalid or incomplete pairings.

Several edge cases are important:

  • The smallest possible input, n = 2, where unhappiness is impossible
  • Situations where everyone is unhappy
  • Situations where nobody is unhappy
  • Cases where a person prefers many others over their partner, but none of those preferences are mutual
  • Cases where preference ranking lookup must be efficient, otherwise repeated scans become expensive

Approaches

Brute Force Approach

A straightforward solution is to directly simulate the definition of unhappiness.

For every person x:

  1. Find their current partner y
  2. Iterate through every other person u
  3. Check whether x prefers u over y
  4. If so, find u's partner v
  5. Check whether u prefers x over v

If both conditions hold, then x is unhappy.

The main issue with a naive brute force solution is preference comparison. If we repeatedly scan preference lists to determine ranking order, each lookup costs O(n) time. Since we already iterate over people and potential preferred friends, this creates an O(n^3) solution.

Although n = 500 is not enormous, cubic complexity is unnecessarily expensive.

Optimal Approach

The key observation is that preference comparisons happen very frequently.

We repeatedly need to answer questions like:

Does person x prefer u over y?

Instead of scanning the preference list every time, we can preprocess ranking positions.

We create a rank[x][u] table where:

  • Smaller values mean higher preference
  • rank[x][u] gives the position of u in x's preference list

Then preference comparison becomes:

rank[x][u] < rank[x][y]

which is an O(1) operation.

We also build a partner array so we can instantly determine each person's assigned partner.

After preprocessing:

  • We iterate through each person
  • Check only the people they prefer more than their current partner
  • Determine whether the preference is mutual

This reduces the overall complexity to O(n^2).

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(n) Repeatedly scans preference lists for ranking checks
Optimal O(n²) O(n²) Uses precomputed ranking table for constant time comparisons

Algorithm Walkthrough

  1. Create a partner array of size n.

This array stores the current partner for every person. If [a, b] appears in pairs, then:

  • partner[a] = b
  • partner[b] = a

This allows constant time partner lookup. 2. Build a ranking matrix.

We create:

rank[x][u]

which stores how much person x likes person u.

Lower values represent stronger preference.

For example:

preferences[0] = [2, 1, 3]

becomes:

rank[0][2] = 0
rank[0][1] = 1
rank[0][3] = 2

This preprocessing allows instant preference comparisons. 3. Iterate through every person x.

For each person, determine their assigned partner y. 4. Check everyone x prefers more than y.

Since preferences are ordered, we can walk through preferences[x] from the beginning until we reach y.

Every person before y is someone x prefers more than their assigned partner. 5. For each preferred person u, determine whether the preference is mutual.

Let:

v = partner[u]

If:

rank[u][x] < rank[u][v]

then u also prefers x over their current partner.

At this point, x is unhappy. 6. Count unhappy people.

As soon as we find one valid u, we increment the answer and stop checking further candidates for x.

Why it works

The algorithm directly implements the formal definition of an unhappy friend.

For each person x, we examine exactly the people that x prefers more than their assigned partner. For each such candidate u, we verify whether u also prefers x over u's own partner.

If both conditions hold, then x satisfies the problem definition of unhappiness.

Because the ranking matrix correctly represents all preference orders, every comparison is accurate. Since every possible qualifying candidate is checked, no unhappy friend can be missed.

Python Solution

from typing import List

class Solution:
    def unhappyFriends(
        self,
        n: int,
        preferences: List[List[int]],
        pairs: List[List[int]]
    ) -> int:

        # partner[x] = current partner of x
        partner = [0] * n

        for x, y in pairs:
            partner[x] = y
            partner[y] = x

        # rank[x][u] = preference order of u for x
        # smaller value means higher preference
        rank = [[0] * n for _ in range(n)]

        for person in range(n):
            for position, friend in enumerate(preferences[person]):
                rank[person][friend] = position

        unhappy_count = 0

        for x in range(n):
            y = partner[x]

            # Check everyone x prefers more than y
            for u in preferences[x]:

                # Once we reach y, everyone after y is less preferred
                if u == y:
                    break

                v = partner[u]

                # u prefers x over current partner v
                if rank[u][x] < rank[u][v]:
                    unhappy_count += 1
                    break

        return unhappy_count

The implementation begins by constructing the partner array so we can instantly determine any person's assigned partner.

Next, the rank matrix is built. This preprocessing step is the main optimization of the solution. Instead of repeatedly scanning preference lists, we convert preference lookup into a constant time array access.

The main loop processes each person independently. For a given person x, we iterate through their preference list until we encounter their current partner y. Because the preference list is sorted from most preferred to least preferred, every person before y is someone x prefers more.

For each candidate u, we retrieve u's partner v and check whether u ranks x higher than v. If that condition is true, x is unhappy and we increment the result immediately.

The break statement is important because the problem only asks whether a person is unhappy, not how many different reasons they are unhappy.

Go Solution

func unhappyFriends(n int, preferences [][]int, pairs [][]int) int {

	partner := make([]int, n)

	for _, pair := range pairs {
		x := pair[0]
		y := pair[1]

		partner[x] = y
		partner[y] = x
	}

	// rank[x][u] = preference order of u for x
	rank := make([][]int, n)

	for i := 0; i < n; i++ {
		rank[i] = make([]int, n)

		for pos, friend := range preferences[i] {
			rank[i][friend] = pos
		}
	}

	unhappyCount := 0

	for x := 0; x < n; x++ {

		y := partner[x]

		for _, u := range preferences[x] {

			// Stop once current partner is reached
			if u == y {
				break
			}

			v := partner[u]

			// u prefers x over v
			if rank[u][x] < rank[u][v] {
				unhappyCount++
				break
			}
		}
	}

	return unhappyCount
}

The Go implementation follows the same logic as the Python version. Slices are used instead of dynamic Python lists. Since Go arrays are fixed size, slices provide the necessary flexibility.

There are no integer overflow concerns because all values are small and bounded by n <= 500.

The ranking matrix is explicitly initialized row by row using nested make calls.

Worked Examples

Example 1

n = 4

preferences =
[
  [1,2,3],
  [3,2,0],
  [3,1,0],
  [1,2,0]
]

pairs =
[
  [0,1],
  [2,3]
]

Step 1: Build partner array

Person Partner
0 1
1 0
2 3
3 2

Step 2: Build ranking table

Person Preference Order
0 1 > 2 > 3
1 3 > 2 > 0
2 3 > 1 > 0
3 1 > 2 > 0

Step 3: Evaluate each person

Person 0

Current partner is 1.

Preference list:

[1,2,3]

We stop immediately because partner 1 appears first.

Person 0 is happy.

Person 1

Current partner is 0.

Preference list before 0:

[3,2]

Check u = 3.

  • 1 prefers 3 over 0
  • 3 is paired with 2
  • 3 prefers 1 over 2

So person 1 is unhappy.

Person 2

Current partner is 3.

Preference list before 3:

[]

Person 2 is happy.

Person 3

Current partner is 2.

Preference list before 2:

[1]

Check u = 1.

  • 3 prefers 1 over 2
  • 1 is paired with 0
  • 1 prefers 3 over 0

So person 3 is unhappy.

Final answer:

2

Example 2

n = 2
preferences = [[1], [0]]
pairs = [[1,0]]

Each person is paired with the only other available person.

Nobody can prefer someone else.

Result:

0

Example 3

n = 4

preferences =
[
  [1,3,2],
  [2,3,0],
  [1,3,0],
  [0,2,1]
]

pairs =
[
  [1,3],
  [0,2]
]

Partner mapping

Person Partner
0 2
1 3
2 0
3 1

Evaluation

Person Preferred Before Partner Unhappy?
0 1, 3 Yes
1 2 Yes
2 1, 3 Yes
3 0, 2 Yes

All four friends are unhappy.

Final answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n²) Building rankings takes O(n²), checking unhappiness also takes O(n²)
Space O(n²) Ranking matrix stores preference order for every pair of people

The ranking matrix dominates the memory usage because it contains n × n entries.

The runtime remains quadratic because each person's preference list is traversed at most once, and every comparison afterward is constant time.

Test Cases

from typing import List

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:

        partner = [0] * n

        for x, y in pairs:
            partner[x] = y
            partner[y] = x

        rank = [[0] * n for _ in range(n)]

        for person in range(n):
            for pos, friend in enumerate(preferences[person]):
                rank[person][friend] = pos

        unhappy = 0

        for x in range(n):
            y = partner[x]

            for u in preferences[x]:
                if u == y:
                    break

                v = partner[u]

                if rank[u][x] < rank[u][v]:
                    unhappy += 1
                    break

        return unhappy

sol = Solution()

# Example 1
assert sol.unhappyFriends(
    4,
    [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]],
    [[0, 1], [2, 3]]
) == 2  # standard mixed case

# Example 2
assert sol.unhappyFriends(
    2,
    [[1], [0]],
    [[1, 0]]
) == 0  # smallest valid input

# Example 3
assert sol.unhappyFriends(
    4,
    [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]],
    [[1, 3], [0, 2]]
) == 4  # everyone unhappy

# Nobody unhappy
assert sol.unhappyFriends(
    4,
    [[1, 2, 3], [0, 2, 3], [3, 1, 0], [2, 1, 0]],
    [[0, 1], [2, 3]]
) == 0  # everyone paired with top choice

# One unhappy friend
assert sol.unhappyFriends(
    4,
    [[1, 2, 3], [2, 0, 3], [1, 0, 3], [0, 1, 2]],
    [[0, 1], [2, 3]]
) == 2  # asymmetric preference interactions

# Larger structured case
assert sol.unhappyFriends(
    6,
    [
        [1, 2, 3, 4, 5],
        [0, 2, 3, 4, 5],
        [1, 0, 3, 4, 5],
        [2, 1, 0, 4, 5],
        [5, 3, 2, 1, 0],
        [4, 3, 2, 1, 0]
    ],
    [[0, 1], [2, 3], [4, 5]]
) == 0  # multiple pairs, all stable

print("All tests passed!")
Test Why
Example 1 Verifies standard unhappy relationship detection
Example 2 Tests smallest valid input
Example 3 Tests scenario where everyone is unhappy
Nobody unhappy Ensures stable pairing returns zero
One unhappy friend Validates partial instability
Larger structured case Confirms correctness on larger input sizes

Edge Cases

Minimum Input Size

When n = 2, there is only one possible pairing. Neither person has an alternative candidate to compare against, so unhappiness is impossible.

A buggy implementation might incorrectly attempt to access nonexistent preference entries or assume there are alternative choices available. The current implementation handles this naturally because the preference loop immediately reaches the assigned partner and exits.

Everyone Is Unhappy

It is possible for every single person to be unhappy simultaneously. This stresses whether the algorithm correctly evaluates each person independently.

A common bug is prematurely stopping the outer loop after finding one unhappy person. The implementation avoids this by only breaking the inner loop for the current person.

Preference Ranking Lookup

Without preprocessing rankings, repeatedly scanning preference lists can become inefficient and error prone.

For example, determining whether:

u prefers x over v

requires comparing relative positions inside u's preference list.

The ranking matrix guarantees constant time comparisons and avoids subtle indexing mistakes that can occur with repeated list scans.