Count Unhappy Friends - Leetcode Solution

The Count Unhappy Friends problem on LeetCode is a type of mathematical problem that requires you to count the number of unhappy friends in a group. In this problem, you are given a set of friends and their preferences for each other. You are also provided the pair of friends who are assigned to each other.

The problem statement is as follows:

There are n friends that are split into two groups: a and b. Each friend is assigned a unique ID starting from 0 to n-1. You are given an integer array preferences, which is of size n x n and represents the liking of the ith friend towards the jth friend, where preferences[i][j] = k means that the ith friend likes the jth friend the most if k == 0, the ith friend likes the jth friend the least if k == n-1, otherwise, the ith friend likes the jth friend a little bit more each time k moves towards n-1. A friend x is unhappy if x is assigned to a group that he/she dislikes the most.

Return the number of unhappy friends.

Input: n = 4, preferences = [[1, 2, 3], [3, 2, 0], [3, 1, 0], [1, 2, 0]], pairs = [[0, 1], [2, 3]] Output: 2 Explanation: Friend 1 is unhappy because he is assigned to be with friend 2 whom he dislikes the most. Friend 3 is unhappy because he is assigned to be with friend 0 whom he dislikes the most.

Solution:

To solve the Count Unhappy Friends problem, we need to first understand the problem statement and the requirements. We have two sets of friends, a and b, and each friend has a unique ID. We are given preferences of friends, which represents the liking of each friend towards each other. The integer array preferences is of size n x n and stores the liking of the ith friend towards the jth friend.

We also have a pair of friends who are assigned to each other. We need to find the number of unhappy friends who are assigned to a group they dislike the most.

We can begin by iterating over each pair of friends and checking if they are unhappy. If a friend is unhappy, we can count the number of unhappy friends.

To check if a friend is unhappy, we can compare their preferences with the friend they are assigned to. If the assigned friend is not the one the current friend likes the most, they are unhappy.

Here's the implementation of the solution in Python:

def unhappyFriends(n, preferences, pairs): # Store the preference of each friend pref = [[0] * n for _ in range(n)] for i in range(n): for j in range(n-1): pref[i][preferences[i][j]] = j

# Store the pair of friends
pair = {}
for p in pairs:
    pair[p[0]] = p[1]
    pair[p[1]] = p[0]

unhappy = 0
for i in range(n):
    j = pair[i]
    for k in range(n):
        if k == i or k == j:
            continue
        if pref[i][k] < pref[i][j] and pref[k][i] < pref[k][pair[k]]:
            unhappy += 1
            break

return unhappy

In this implementation, we first store the preference of each friend in a 2D array pref. We then store the pair of friends in a dictionary pair.

We then iterate over each friend and check if they are unhappy. If a friend is unhappy, we increase the count of unhappy friends.

We check if a friend is unhappy by comparing their preferences with the friend they are assigned to. If the assigned friend is not the one the current friend likes the most, they are unhappy. We break the loop once we find an unhappy friend.

We return the count of unhappy friends as the result.

The time complexity of this solution is O(n^2) and the space complexity is O(n^2).

1