Problem Description

You have n friends (where n is always even) who need to be paired up. Each friend has a preference list that ranks all other friends from most preferred to least preferred.

Given:

• preferences[i]: A list for friend i containing all other friends sorted by preference (earlier in the list = more preferred)
• pairs: The actual pairings, where pairs[i] = [xi, yi] means friend xi is paired with friend yi

A friend x becomes unhappy when both of these conditions are true:

1. Friend x is paired with y, but x prefers some other friend u more than y
2. That friend u is paired with v, but u also prefers x more than their current partner v

In other words, x and u would both rather be paired with each other than with their current partners.

The task is to count how many friends are unhappy with the given pairing arrangement.

For example, if friend 0 is paired with friend 1, but friend 0 prefers friend 2 more than friend 1, AND friend 2 (who is paired with friend 3) prefers friend 0 more than friend 3, then friend 0 is unhappy. The same logic would also make friend 2 unhappy in this scenario.

The solution uses a dictionary d to store preference rankings (where d[i][j] represents the rank/position of friend j in friend i's preference list), and another dictionary p to track who each friend is paired with. It then checks each friend to see if they have a mutual preference with someone other than their current partner.

Intuition

The key insight is that we need to efficiently check if there exists a "mutual preference" situation - where two friends would rather be with each other than their current partners.

To determine if friend x is unhappy, we need to:

1. Find all friends that x prefers more than their current partner y
2. For each such friend u, check if u also prefers x over their current partner v

The challenge is doing these preference comparisons quickly. If we use the raw preference lists, checking "does x prefer u over y?" would require searching through x's preference list to find the positions of both u and y, then comparing them.

This is where the preprocessing becomes crucial. By converting each preference list into a dictionary that maps friend -> ranking, we can answer "how much does x prefer u?" in O(1) time. Specifically, d[x][u] gives us the rank of u in x's preference list (where smaller rank = more preferred).

With this structure:

• To check if x prefers u over y: we compare d[x][u] < d[x][y]
• To check if u prefers x over v: we compare d[u][x] < d[u][v]

The algorithm then becomes straightforward: for each friend x paired with y, we iterate through all friends that x ranked higher than y (those with rank less than d[x][y]). For each such friend u, we check if the preference is mutual. If we find even one such mutual preference, x is unhappy and we can stop checking further.

This approach works because we only need to find if at least one "better mutual match" exists for a friend to be unhappy - we don't need to find all such matches.

Solution Approach

The implementation uses two key data structures to efficiently solve the problem:

1. Building the Preference Ranking Dictionary

First, we create a list of dictionaries d where d[i] maps each friend to their ranking in friend i's preference list:

d = [{x: j for j, x in enumerate(p)} for p in preferences]

This transforms the preference lists into a format where we can quickly look up rankings. For example, if preferences[0] = [3, 1, 2], then d[0] = {3: 0, 1: 1, 2: 2}, meaning friend 0 ranks friend 3 at position 0 (most preferred).

2. Creating the Pairing Map

We build a dictionary p to store who each friend is paired with:

p = {}
for x, y in pairs:
    p[x] = y
    p[y] = x

This bidirectional mapping allows us to quickly find any friend's partner.

3. Counting Unhappy Friends

For each friend x from 0 to n-1:

• Find their current partner: y = p[x]
• Get the ranking of the current partner: d[x][y]
• Check all friends that x prefers more than y (those with ranking less than d[x][y]):

  for i in range(d[x][y]):
      u = preferences[x][i]  # Get the friend at ranking i

• For each such preferred friend u:
  • Find u's current partner: v = p[u]
  • Check if u also prefers x over their current partner v:

    if d[u][x] < d[u][v]:
        ans += 1
        break

  • If the condition is met, x is unhappy. We increment the counter and break (since we only need to find one such mutual preference)

The time complexity is O(n²) in the worst case, where we might check all pairs of friends. The space complexity is O(n²) for storing the preference rankings dictionary.

Example Walkthrough

Let's walk through a small example with 4 friends (n=4).

Given:

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

This means:

• Friend 0 prefers: 1 > 3 > 2
• Friend 1 prefers: 2 > 3 > 0
• Friend 2 prefers: 1 > 3 > 0
• Friend 3 prefers: 0 > 2 > 1

And the pairings are: (0,2) and (1,3)

Step 1: Build the preference ranking dictionary d

d[0] = {1: 0, 3: 1, 2: 2}  # Friend 0 ranks friend 1 at position 0
d[1] = {2: 0, 3: 1, 0: 2}  # Friend 1 ranks friend 2 at position 0
d[2] = {1: 0, 3: 1, 0: 2}  # Friend 2 ranks friend 1 at position 0
d[3] = {0: 0, 2: 1, 1: 2}  # Friend 3 ranks friend 0 at position 0

Step 2: Create the pairing map p

p = {1: 3, 3: 1, 0: 2, 2: 0}

Step 3: Check each friend for unhappiness

Friend 0:

• Current partner: y = p[0] = 2
• Rank of current partner: d[0][2] = 2
• Check friends ranked better than 2 (positions 0 and 1):
  • Position 0: u = 1
    • u's partner: v = p[1] = 3
    • Does friend 1 prefer 0 over 3? d[1][0] = 2, d[1][3] = 1
    • Since 2 > 1, friend 1 does NOT prefer 0 over 3
  • Position 1: u = 3
    • u's partner: v = p[3] = 1
    • Does friend 3 prefer 0 over 1? d[3][0] = 0, d[3][1] = 2
    • Since 0 < 2, friend 3 DOES prefer 0 over 1
    • Friend 0 is unhappy! (break)

Friend 1:

• Current partner: y = p[1] = 3
• Rank of current partner: d[1][3] = 1
• Check friends ranked better than 1 (position 0):
  • Position 0: u = 2
    • u's partner: v = p[2] = 0
    • Does friend 2 prefer 1 over 0? d[2][1] = 0, d[2][0] = 2
    • Since 0 < 2, friend 2 DOES prefer 1 over 0
    • Friend 1 is unhappy! (break)

Friend 2:

• Current partner: y = p[2] = 0
• Rank of current partner: d[2][0] = 2
• Check friends ranked better than 2 (positions 0 and 1):
  • Position 0: u = 1
    • u's partner: v = p[1] = 3
    • Does friend 1 prefer 2 over 3? d[1][2] = 0, d[1][3] = 1
    • Since 0 < 1, friend 1 DOES prefer 2 over 3
    • Friend 2 is unhappy! (break)

Friend 3:

• Current partner: y = p[3] = 1
• Rank of current partner: d[3][1] = 2
• Check friends ranked better than 2 (positions 0 and 1):
  • Position 0: u = 0
    • u's partner: v = p[0] = 2
    • Does friend 0 prefer 3 over 2? d[0][3] = 1, d[0][2] = 2
    • Since 1 < 2, friend 0 DOES prefer 3 over 2
    • Friend 3 is unhappy! (break)

Result: All 4 friends are unhappy in this pairing arrangement.

This example illustrates how mutual preferences create unhappiness: Friend 0 and 3 would prefer each other, and friends 1 and 2 would prefer each other, making everyone unhappy with their current pairings.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n²)

The algorithm consists of several parts:

• Building the dictionary d: This involves iterating through n preference lists, each containing n-1 elements. Creating a dictionary for each person takes O(n) time, so total is O(n²).
• Building the pairing dictionary p: Iterating through n/2 pairs takes O(n) time.
• Main loop: For each person x (n iterations):
  • In the worst case, we iterate through all friends in their preference list before y, which could be up to n-1 friends
  • For each friend u, we perform constant time lookups in dictionaries p and d
  • This gives us O(n) per person, resulting in O(n²) total

The dominant operation is O(n²), giving us an overall time complexity of O(n²).

Space Complexity: O(n²)

The space usage breaks down as:

• Dictionary d: Stores n dictionaries, each containing n-1 key-value pairs, using O(n²) space total
• Dictionary p: Stores n key-value pairs, using O(n) space
• The input preferences array itself uses O(n²) space (though this is typically not counted as auxiliary space)
• Other variables (ans, loop variables) use O(1) space

The dominant space requirement is O(n²) from dictionary d, giving us an overall space complexity of O(n²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Break Statement Placement

A critical pitfall is forgetting or misplacing the break statement after finding that a person is unhappy. Once we determine that person x is unhappy (by finding even one person u with whom there's a mutual preference), we must immediately break out of the inner loop.

Incorrect Implementation:

for rank in range(rank_of_y):
    preferred_person_u = preferences[person_x][rank]
    partner_v = partner_map[preferred_person_u]
    if preference_rank[preferred_person_u][person_x] < preference_rank[preferred_person_u][partner_v]:
        unhappy_count += 1
        # Missing break here - would count x multiple times!

Why it's wrong: Without the break, if person x has mutual preferences with multiple other people, they would be counted as unhappy multiple times. The problem asks for the number of unhappy friends, not the number of unhappy relationships.

Correct Implementation:

for rank in range(rank_of_y):
    preferred_person_u = preferences[person_x][rank]
    partner_v = partner_map[preferred_person_u]
    if preference_rank[preferred_person_u][person_x] < preference_rank[preferred_person_u][partner_v]:
        unhappy_count += 1
        break  # Critical: stop checking once we know x is unhappy

2. Incorrectly Building the Preference Ranking Dictionary

Another common mistake is confusing the index with the value when building the ranking dictionary.

Incorrect Implementation:

# Wrong: Maps rank to friend instead of friend to rank
preference_rank = []
for person_preferences in preferences:
    rank_dict = {}
    for rank, friend in enumerate(person_preferences):
        rank_dict[rank] = friend  # Wrong mapping direction!
    preference_rank.append(rank_dict)

Why it's wrong: This creates a dictionary that tells us "who is at rank i" rather than "what rank does friend j have". We need to look up rankings by friend ID, not the other way around.

Correct Implementation:

# Correct: Maps friend to their rank
preference_rank = []
for person_preferences in preferences:
    rank_dict = {}
    for rank, friend in enumerate(person_preferences):
        rank_dict[friend] = rank  # Friend -> Rank mapping
    preference_rank.append(rank_dict)

3. Off-by-One Error in Preference Comparison

Be careful with the inequality comparisons when checking preferences.

Incorrect Implementation:

# Wrong: Using <= instead of <
if preference_rank[preferred_person_u][person_x] <= preference_rank[preferred_person_u][partner_v]:
    unhappy_count += 1
    break

Why it's wrong: Using <= would incorrectly count cases where u is indifferent between x and their current partner v (same ranking). The problem requires that both people strictly prefer each other over their current partners.

Correct Implementation:

# Correct: Strict inequality ensures u truly prefers x over v
if preference_rank[preferred_person_u][person_x] < preference_rank[preferred_person_u][partner_v]:
    unhappy_count += 1
    break