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. In other words, a friend earlier in the list is more preferred than a friend later in the list. Friends in each list are denoted by integers from 0 to n-1.
All the friends are divided into pairs. The pairings are given in a list pairs, where pairs[i] = [xi, yi] denotes xi is paired with yi and yi is paired with xi.
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.
 
Example 1:
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:
- 1 is paired with 0 but prefers 3 over 0, and
- 3 prefers 1 over 2.
Friend 3 is unhappy because:
- 3 is paired with 2 but prefers 1 over 2, and
- 1 prefers 3 over 0.
Friends 0 and 2 are happy.

Example 2:
Input: n = 2, preferences = [[1], [0]], pairs = [[1, 0]]
Output: 0
Explanation: Both friends 0 and 1 are happy.

Example 3:
Input: n = 4, preferences = [[1, 3, 2], [2, 3, 0], [1, 3, 0], [0, 2, 1]], pairs = [[1, 3], [0, 2]]
Output: 4

 
Constraints:

2 <= n <= 500
n is even.
preferences.length == n
preferences[i].length == n - 1
0 <= preferences[i][j] <= n - 1
preferences[i] does not contain i.
All values in preferences[i] are unique.
pairs.length == n/2
pairs[i].length == 2
xi != yi
0 <= xi, yi <= n - 1
Each person is contained in exactly one pair.

Difficulty: interview

Starter code:

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        

Solutions:
class Solution:
    def preferences_to_scores(self, preferences):
        scores = {}
        for u, up in enumerate(preferences):
            for s, v in enumerate(up):
                scores[(u, v)] = s
        return scores
    
    def unhappy_friends(self, scores, a, b):
        ret = set()
        for ai, aa in enumerate(a):
            af = a[1 - ai]
            for bi, bb in enumerate(b):
                bf = b[1 - bi]
                if scores[(aa, bb)] < scores[(aa, af)] and scores[(bb, aa)] < scores[(bb, bf)]:
                    ret.add(aa)
                    ret.add(bb)
        return ret
    
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        scores = self.preferences_to_scores(preferences)
        ret = set()
        for i, a in enumerate(pairs):
            for j in range(i):
                b = pairs[j]
                ret |= self.unhappy_friends(scores, a, b)
        return len(ret)


class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        
        preference_list = [[0 for _ in range(n)] for _ in range(n)]
        
        for x in range(n):
            for i, y in enumerate(preferences[x]):
                preference_list[x][y] = n-i-1
            
        #print(preference_list)
        unhappy={}
        for i in range(n//2):
            x,y = pairs[i]
            for j in range(n//2):
                u,v = pairs[j]
                if i!=j:
                    if ((preference_list[x][y]<preference_list[x][u] and preference_list[u][x]>preference_list[u][v]) or (preference_list[x][y]<preference_list[x][v] and preference_list[v][u]<preference_list[v][x])):
                        #print(f'X-> x, y : {x, y}; u,v: {u,v}')
                        unhappy[x]=1
                    if ((preference_list[y][x]<preference_list[y][u] and preference_list[u][y]>preference_list[u][v]) or (preference_list[y][x]<preference_list[y][v] and preference_list[v][u]<preference_list[v][y])):
                        #print(f'Y->  y,x : {y,x}; u,v: {u,v}')
                        unhappy[y]=1
        #print(unhappy)
        res = len(unhappy)
            
        return res

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        pref = {}
        for i in range(len(preferences)):
            pref[i] = {}
            plist = preferences[i]
            for j in range(len(plist)):
                pref[i][plist[j]] = j
        print(pref)
            
        unhappy = set()
        for i in range(len(pairs)):
            for j in range(len(pairs)):                
                if i == j:
                    continue
                for x in pairs[i]:
                    y = pairs[i][1] if x == pairs[i][0] else pairs[i][0]
                    for u in pairs[j]:
                        v = pairs[j][1] if u == pairs[j][0] else pairs[j][0]
                        if (pref[x][y] > pref[x][u] and pref[u][v] > pref[u][x]):
                            unhappy.add(x)



        return len(unhappy)

class Solution:
    def unhappyFriends(self, n: int, P: List[List[int]], A: List[List[int]]) -> int:
        # O(n^3)
        # have to look at nC2 pairs
        unhappy = set()
        for i in range(n//2):
            for j in range(i+1,n//2):
                Ai0, Ai1, Aj0, Aj1 = A[i][0], A[i][1], A[j][0], A[j][1]
                # check all 4 poss
                # O(n)
                if P[Ai0].index(Ai1) > P[Ai0].index(Aj0) and P[Aj0].index(Aj1) > P[Aj0].index(Ai0):
                    unhappy.add(Ai0)
                    unhappy.add(Aj0)
                    
                Ai0, Ai1, Aj0, Aj1 = A[i][1], A[i][0], A[j][0], A[j][1]
                # check all 4 poss
                # O(n)
                if P[Ai0].index(Ai1) > P[Ai0].index(Aj0) and P[Aj0].index(Aj1) > P[Aj0].index(Ai0):
                    unhappy.add(Ai0)
                    unhappy.add(Aj0)
                    
                Ai0, Ai1, Aj0, Aj1 = A[i][0], A[i][1], A[j][1], A[j][0]
                # check all 4 poss
                # O(n)
                if P[Ai0].index(Ai1) > P[Ai0].index(Aj0) and P[Aj0].index(Aj1) > P[Aj0].index(Ai0):
                    unhappy.add(Ai0)
                    unhappy.add(Aj0)
                    
                Ai0, Ai1, Aj0, Aj1 = A[i][1], A[i][0], A[j][1], A[j][0]
                # check all 4 poss
                # O(n)
                if P[Ai0].index(Ai1) > P[Ai0].index(Aj0) and P[Aj0].index(Aj1) > P[Aj0].index(Ai0):
                    unhappy.add(Ai0)
                    unhappy.add(Aj0)
                
                    
        return len(unhappy)

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        unhappy = [0] * n
        for i in range(n//2):
            a, b = pairs[i]
            b_a_idx, a_b_idx = preferences[b].index(a), preferences[a].index(b)
            for j in range(i+1, n//2):
                c, d = pairs[j]
                c_a_idx = preferences[c].index(a)
                c_b_idx = preferences[c].index(b)
                c_d_idx = preferences[c].index(d)
                
                d_a_idx = preferences[d].index(a) 
                d_b_idx = preferences[d].index(b) 
                d_c_idx = preferences[d].index(c) 
                
                a_c_idx = preferences[a].index(c) 
                a_d_idx = preferences[a].index(d) 
                
                b_c_idx = preferences[b].index(c) 
                b_d_idx = preferences[b].index(d) 
                
                # a <-> c
                if c_a_idx < c_d_idx and a_c_idx < a_b_idx: unhappy[a] = unhappy[c] = 1
                # a <-> d
                if d_a_idx < d_c_idx and a_d_idx < a_b_idx: unhappy[a] = unhappy[d] = 1
                # b <-> c
                if c_b_idx < c_d_idx and b_c_idx < b_a_idx: unhappy[b] = unhappy[c] = 1
                # b <-> d
                if d_b_idx < d_c_idx and b_d_idx < b_a_idx: unhappy[b] = unhappy[d] = 1
        return sum(unhappy)


class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        unhappy = [0] * n
        for i in range(n//2):
            a, b = pairs[i]
            b_a_idx, a_b_idx = preferences[b].index(a), preferences[a].index(b)
            for j in range(i+1, n//2):
                c, d = pairs[j]
                c_a_idx = preferences[c].index(a)
                c_b_idx = preferences[c].index(b)
                c_d_idx = preferences[c].index(d)
                
                d_a_idx = preferences[d].index(a) 
                d_b_idx = preferences[d].index(b) 
                d_c_idx = preferences[d].index(c) 
                
                a_c_idx = preferences[a].index(c) 
                a_d_idx = preferences[a].index(d) 
                
                b_c_idx = preferences[b].index(c) 
                b_d_idx = preferences[b].index(d) 
                
                # a-c
                if c_a_idx < c_d_idx and a_c_idx < a_b_idx: 
                    unhappy[a] = unhappy[c] = 1
                # a-d
                if d_a_idx < d_c_idx and a_d_idx < a_b_idx: 
                    unhappy[a] = unhappy[d] = 1
                # b-c
                if c_b_idx < c_d_idx and b_c_idx < b_a_idx: 
                    unhappy[b] = unhappy[c] = 1
                # b-d
                if d_b_idx < d_c_idx and b_d_idx < b_a_idx: 
                    unhappy[b] = unhappy[d] = 1
        return sum(unhappy)


class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        idx_table = collections.defaultdict(lambda: collections.defaultdict(int))
        for i in range(n):
            for idx, person in enumerate(preferences[i]): idx_table[i][person] = idx
                
        unhappy = [0] * n
        for i in range(n//2):
            a, b = pairs[i]
            b_a_idx, a_b_idx = idx_table[b][a], idx_table[a][b]
            for j in range(i+1, n//2):
                c, d = pairs[j]
                
                c_a_idx = idx_table[c][a]
                c_b_idx = idx_table[c][b]
                c_d_idx = idx_table[c][d]
                
                d_a_idx = idx_table[d][a] 
                d_b_idx = idx_table[d][b] 
                d_c_idx = idx_table[d][c] 
                
                a_c_idx = idx_table[a][c] 
                a_d_idx = idx_table[a][d] 
                
                b_c_idx = idx_table[b][c] 
                b_d_idx = idx_table[b][d] 
                
                if c_a_idx < c_d_idx and a_c_idx < a_b_idx: unhappy[a] = unhappy[c] = 1 # a & c prefer each other
                if d_a_idx < d_c_idx and a_d_idx < a_b_idx: unhappy[a] = unhappy[d] = 1 # a & d prefer each other
                if c_b_idx < c_d_idx and b_c_idx < b_a_idx: unhappy[b] = unhappy[c] = 1 # b & c prefer each other
                if d_b_idx < d_c_idx and b_d_idx < b_a_idx: unhappy[b] = unhappy[d] = 1 # b & d prefer each other
        return sum(unhappy)

class Solution:
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        res = set()
        mem = [[0 for _ in range(n)] for _ in range(n)]
        
        for i in range(n):
            for j in range(n-1):
                mem[i][preferences[i][j]] = j+1
        
        for i in range(n//2):
            x = pairs[i][0]
            y = pairs[i][1]
            for j in range(i+1, n//2):
                u = pairs[j][0]
                v = pairs[j][1]
                if mem[x][u] < mem[x][y] and mem[u][x] < mem[u][v]:
                    res.add(x)
                    res.add(u)
                if mem[x][v] < mem[x][y] and mem[v][x] < mem[v][u]:
                    res.add(x)
                    res.add(v)
                if mem[y][u] < mem[y][x] and mem[u][y] < mem[u][v]:
                    res.add(y)
                    res.add(u)
                if mem[y][v] < mem[y][x] and mem[v][y] < mem[v][u]:
                    res.add(y)
                    res.add(v)

        return len(res)

import numpy as np

class Solution:    
    
    def check_happy(self,x,y,u,v,fmatrix,unhappy): 
        if(fmatrix[x][u]>fmatrix[x][y] and fmatrix[u][x]>fmatrix[u][v]):
            unhappy.add(x)
            unhappy.add(u)
   
    def unhappyFriends(self, n, preferences, pairs) -> int:
        if(n==2):
            return 0
        unhappy = set()
        fmatrix = np.zeros((n,n),dtype=int)
        for i,friendpref in enumerate(preferences):
            for j,pref_ind in enumerate(friendpref):
                fmatrix[i][pref_ind] = n-1-j

        for i in range(n//2-1):
            for j in range(i+1, n//2):
                x,y,u,v = pairs[i][0],pairs[i][1],pairs[j][0],pairs[j][1]
                self.check_happy(x,y,u,v,fmatrix,unhappy)
                self.check_happy(x,y,v,u,fmatrix,unhappy)
                self.check_happy(y,x,u,v,fmatrix,unhappy)
                self.check_happy(y,x,v,u,fmatrix,unhappy)
                
                    
        return len(unhappy)

import numpy as np

class Solution:    
    
    def check_happy(self,x,y,u,v,fmatrix,unhappy): 
        if(fmatrix[x][u]>fmatrix[x][y] and fmatrix[u][x]>fmatrix[u][v]):
            unhappy.add(x)
            unhappy.add(u)
   
    def unhappyFriends(self, n, preferences, pairs) -> int:
        unhappy = set()
        fmatrix = np.zeros((n,n),dtype=int)
        for i,friendpref in enumerate(preferences):
            for j,pref_ind in enumerate(friendpref):
                fmatrix[i][pref_ind] = n-1-j

        for i in range(n//2-1):
            for j in range(i+1, n//2):
                x,y,u,v = pairs[i][0],pairs[i][1],pairs[j][0],pairs[j][1]
                self.check_happy(x,y,u,v,fmatrix,unhappy)
                self.check_happy(x,y,v,u,fmatrix,unhappy)
                self.check_happy(y,x,u,v,fmatrix,unhappy)
                self.check_happy(y,x,v,u,fmatrix,unhappy)
                
                    
        return len(unhappy)

class Solution:
    
    
    def get_pair(self, i):
        for j in self.pairs:
            if i in j:
                for k in j:
                    if k != i:
                        return k
                    
                    
    def t_happy(self, t, i):
        pair = self.get_pair(t)
        for j in self.prefer[t]:
            if j == pair:
                return True
            if j == i:
                return False
                    
                    
    def happy(self, i, p):
        prefer = self.prefer[i]
        if prefer[0] == p:
            return True
        for j in range(1, len(prefer)):
            if not self.t_happy(prefer[j-1], i):
                return False
            if prefer[j] == p:
                return True

    
    
    def unhappyFriends(self, n: int, preferences: List[List[int]], pairs: List[List[int]]) -> int:
        self.prefer = preferences
        self.pairs = pairs
        count = 0
        for i in range(n):
            p = self.get_pair(i)
            if not self.happy(i, p):
                count += 1
        return count