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.

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