Taro Logo

Count Unhappy Friends

Medium
Asked by:
Profile picture
0 views
Topics:
Arrays
Given an integer n representing the number of friends, a 2D integer array `preferences` where `preferences[i]` contains the list of friends in the order of preference for the i-th friend, and a 2D integer array `pairs` where each `pairs[i] = [x, y]` indicates that the friend `x` is paired with the friend `y`.

A friend `x` is considered unhappy if `x` is paired with `y` but has another friend `u` in their preference list who prefers `x` over their own partner and `u` prefers `x` over `u`'s own partner.

Calculate the number of unhappy friends.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. What are the constraints on `n` (the number of friends), and the sizes of the `preferences` and `pairs` arrays? I'm interested in the maximum possible values.
  2. Can I assume that the `preferences` list for each friend contains all other friends exactly once, and that the pairs are valid (i.e., each friend appears in exactly one pair)?
  3. Is the preference order in `preferences[i]` from most preferred to least preferred, or vice-versa? In other words, is `preferences[i][0]` the most preferred friend for friend `i`?
  4. If a friend `x` has no friends `u` who are preferred and also prefer `x` over their partners, should I consider `x` as unhappy?
  5. If there are multiple 'unhappy' conditions met for a single friend, should that friend be counted multiple times or only once toward the final count?

Brute Force Solution

Approach

The brute force approach here means we will look at each person individually and see if they are unhappy. To determine if a person is unhappy, we will examine all possible alternative pairings they could have with others.

Here's how the algorithm would work step-by-step:

  1. For each person, find who they are currently paired with.
  2. Go through the list of their preferences, one person at a time.
  3. For each person in their preference list, see if *that* person also has a preference for our original person *over* their current partner.
  4. If we find such a person, our original person is unhappy and we count them.
  5. After checking all people and counting the unhappy ones, we have our answer.

Code Implementation

def count_unhappy_friends_brute_force(
    number_of_friends,
    pairs,
    preference
):
    unhappy_friends_count = 0

    for friend_index in range(number_of_friends):
        is_unhappy = False
        partner_index = pairs[friend_index] 

        # Iterate through preferred friends to check unhappiness
        for preferred_friend_index in preference[friend_index]:
            if preferred_friend_index == partner_index:
                break

            partner_of_preferred_friend =
                pairs[preferred_friend_index]

            # Check if the preferred friend also prefers the current friend
            for friend_in_preferred_friend_preference in \
                preference[preferred_friend_index]:

                if (friend_in_preferred_friend_preference ==
                        friend_index):

                    # If preferred friend prefers current friend and current friend prefers the preferred friend
                    # then mark current friend as unhappy
                    if friend_in_preferred_friend_preference !=
                            partner_of_preferred_friend:

                        is_unhappy = True
                        break

                elif (friend_in_preferred_friend_preference ==
                        partner_of_preferred_friend):
                    break

            if is_unhappy:
                unhappy_friends_count += 1
                break

    return unhappy_friends_count

Big(O) Analysis

Time Complexity
O(n²) – The outer loop iterates through each person, which takes O(n) time where n is the number of people. The inner loop iterates through the preference list of each person. In the worst case, each person's preference list could contain up to n-1 other people. For each preferred person, we also need to check their preference list, which could also take up to O(n) time. Therefore, the overall time complexity is O(n * n), simplifying to O(n²).
Space Complexity
O(1) – The given algorithm's space complexity is constant, O(1). The description focuses on iterating and comparing existing data; it doesn't create any auxiliary data structures that scale with the input size. It uses only a few variables to track the current person and their preferences during the nested loops but the number of variables remains constant regardless of the input size N (number of friends) or the size of the preferences lists.

Optimal Solution

Approach

The problem asks us to find unhappy friends based on their preferences and pairings. The key is to directly check the conditions for unhappiness for each person, instead of exhaustively searching for unhappy pairs.

Here's how the algorithm would work step-by-step:

  1. First, store each person's preferences in a way that makes it quick to look up how much someone likes another person.
  2. Next, look at each pair of friends to see if either of them is unhappy.
  3. To check if a friend is unhappy, see if they have someone they prefer more than their current partner.
  4. If they do, check if that preferred person also prefers the original friend to their own partner.
  5. If both those conditions are true, then the original friend is unhappy. Keep track of each unhappy friend you find.
  6. Finally, count the number of unique unhappy friends and return that count.

Code Implementation

def count_unhappy_friends(number_of_friends, preferences, pairs):
    paired_with = [0] * number_of_friends
    for pair in pairs:
        person1, person2 = pair
        paired_with[person1] = person2
        paired_with[person2] = person1

    unhappy_count = 0
    for person in range(number_of_friends):
        for preferred_friend in preferences[person]:
            # If the preferred friend is the current partner, move on
            if preferred_friend == paired_with[person]:
                break

            preferred_friend_partner = paired_with[preferred_friend]

            # Check if the preferred friend also prefers the person over their partner
            for potential_better_match in preferences[preferred_friend]:

                # If the potential match is their current partner, move on.
                if potential_better_match == preferred_friend_partner:
                    break

                # If the preferred friend prefers the person, the person is unhappy
                if potential_better_match == person:
                    unhappy_count += 1

                    # Count each person only once
                    break

        # Count each person only once
        if unhappy_count > 0 and paired_with[person] in preferences[person]:
            continue

    return unhappy_count

Big(O) Analysis

Time Complexity
O(n²) – The algorithm iterates through the 'pairs' array, which has a length of n/2, in the worst case (where n is the number of friends). Inside this loop, for each friend in a pair, it iterates through their preference list (of maximum length n-1) to find a preferred friend. Then, for each preferred friend, it checks if that friend also prefers the original friend over their current partner. The nested loop structure results in approximately (n/2) * (n-1) operations, which simplifies to O(n²).
Space Complexity
O(N^2) – The dominant space complexity stems from storing each person's preferences in a way that allows for quick lookup. This is typically implemented using a matrix or a hashmap for each person, requiring space to store the preference rankings. Since each person needs to know their preference for every other person, and there are N people, this results in an auxiliary data structure of size N * N, or N^2. Other variables used to track unhappy friends use constant space and are insignificant compared to the preference matrix.

Edge Cases

n = 1: Only one friend exists.
How to Handle:
Return 0, as a single person cannot be unhappy since pairings require two people.
Empty 'preferences' or 'pairs' arrays.
How to Handle:
Return 0 since without preferences or pairs, no unhappy friends can be determined.
preferences[i] is empty for some i.
How to Handle:
Treat an empty preference list as if the friend prefers nobody, thereby having no unhappy friends due to that preference.
pairs contains duplicate pairs (e.g., [1, 2] and [2, 1]).
How to Handle:
The algorithm should treat [1,2] and [2,1] as the same pairing, and the implementation should avoid double-counting or creating inconsistencies.
preferences[i] does not contain all other friends.
How to Handle:
The algorithm should handle cases where not all friends are included in the preference list as if those missing friends are the least preferred.
A friend is paired with themselves (e.g., [x, x]).
How to Handle:
The algorithm should handle this by appropriately not considering the friend to be unhappy in such a case as preference still exist toward others.
n is large, and the 'preferences' array has long lists for each friend.
How to Handle:
The algorithm should be optimized to avoid excessive looping or copying of the 'preferences' data (e.g. use efficient lookup).
Friend index is out of range (e.g., an index >= n appears in 'preferences' or 'pairs').
How to Handle:
The algorithm should handle this by throwing an exception or treating as invalid data, and the interviewer should define what the correct behavior is.