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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Unhappy Friends

Number: 1705

Difficulty: Medium

Paid? No

Companies: Bloomberg

Problem Description

Given a list of friend preferences and a set of pairings, determine the number of unhappy friends. A friend x is unhappy if there exists another friend u (paired with v) such that x prefers u over x’s paired friend y, and u also prefers x over u’s paired friend v.

Key Insights

  • Create a quick lookup for each friend’s pair using a mapping.
  • Precompute a ranking for each friend’s preferences to compare the ordering efficiently.
  • For each friend x, iterate over the friends x prefers more than x’s paired friend.
  • For each such friend u, check if u also favors x over u’s partner.
  • Stop early for a friend once an unhappy condition is found.

Space and Time Complexity

Time Complexity: O(n^2), where n is the number of friends. We iterate through each friend’s preference list until their pair is encountered. Space Complexity: O(n^2) for storing the ranking of preferences for each friend.

Solution

We first create a dictionary (or array) pairMapping to quickly find a friend’s paired partner. Next, we build a ranking matrix (or dictionary) for each friend so that given any two friends, we can determine who is more preferred. For each friend x, we traverse x’s list of preferences up to the point where x’s pair appears. For every friend u in this loop, we check if u prefers x over u’s paired friend by comparing their ranking values. If both conditions are satisfied, friend x is marked as unhappy. Finally, we count and return the total number of unhappy friends.

Code Solutions

# Python solution with detailed comments

class Solution:
    def unhappyFriends(self, n: int, preferences: list[list[int]], pairs: list[list[int]]) -> int:
        # Build a dictionary to map each friend to their paired friend
        pairMapping = {}
        for x, y in pairs:
            pairMapping[x] = y
            pairMapping[y] = x

        # Create a ranking matrix to quickly lookup the preference order for each friend
        rank = [[0]*n for _ in range(n)]
        for i in range(n):
            # For each friend, assign a rank to every other friend in its preference list
            for j, friend in enumerate(preferences[i]):
                rank[i][friend] = j

        unhappy_count = 0
        # Check each friend to see if they are unhappy
        for x in range(n):
            y = pairMapping[x]  # x's paired friend
            # Iterate over all friends x prefers more than y
            for u in preferences[x]:
                # Stop if we reach the paired friend y
                if u == y:
                    break
                v = pairMapping[u]  # u's paired friend
                # If u prefers x over its own pair, mark x as unhappy
                if rank[u][x] < rank[u][v]:
                    unhappy_count += 1
                    break  # No need to check further for x
        return unhappy_count

# Example usage:
# sol = Solution()
# print(sol.unhappyFriends(4, [[1,2,3], [3,2,0], [3,1,0], [1,2,0]], [[0,1], [2,3]]))
← Back to All Questions