We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Unhappy Friends

Difficulty: Medium

Problem Description

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. Friends in each list are denoted by integers from 0 to n-1. All the friends are divided into pairs. 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.

Key Insights

  • Each friend has a preference list indicating who they favor.
  • A friend can be unhappy if they are paired with someone they prefer less than another friend who also prefers them over their current partner.
  • The problem can be solved by checking each pairing for potential unhappy conditions.

Space and Time Complexity

Time Complexity: O(n^2) - For each friend, we may need to check their preferences against the preferences of all friends. Space Complexity: O(n) - To store the preferences and the pairs.

Solution

To solve the problem, we follow these steps:

  1. Create a mapping of each friend's preferences to allow for O(1) lookups.
  2. Iterate through each pair to check if either friend in the pair is unhappy.
  3. For a given friend x paired with y, check each of their preferences to see if there exists a friend u paired with v that would make x unhappy.
  4. Count and return the number of unhappy friends.

Code Solutions

def countUnhappyFriends(n, preferences, pairs):
    # Create a preference map for quick access
    preference_map = [None] * n
    for i in range(n):
        preference_map[i] = {friend: idx for idx, friend in enumerate(preferences[i])}
    
    unhappy_count = 0
    # Iterate through each pair
    for x, y in pairs:
        # Check if x is unhappy
        for u in preferences[x]:
            if u == y:  # If u is y, we skip as x can't be unhappy with y
                break
            # Check if u prefers x over their partner v
            v = pairs[u][0] if pairs[u][1] == x else pairs[u][1]
            if preference_map[u][x] < preference_map[u][v]:  # u prefers x over v
                unhappy_count += 1
                break  # No need to check further for x
        # Check if y is unhappy
        for u in preferences[y]:
            if u == x:  # If u is x, we skip as y can't be unhappy with x
                break
            # Check if u prefers y over their partner v
            v = pairs[u][0] if pairs[u][1] == y else pairs[u][1]
            if preference_map[u][y] < preference_map[u][v]:  # u prefers y over v
                unhappy_count += 1
                break  # No need to check further for y
    return unhappy_count
← Back to All Questions