Given a list of the friendship preferences of n friends, where n is always even.

For each friend i, preferences[i] contains a list of friends ordered from most preferred to least preferred. In other words, a friend appearing earlier in the list is preferred by i over a friend appearing later. Each friend is represented by an integer between 0 and n-1.

All friends are split into pairs, given by the list pairs, where pairs[i] = [xi, yi] means that xi is paired with yi, and yi is paired with xi.

However, this pairing may make some friends unhappy. If x is paired with y and u is paired with v, then x is unhappy if both of the following conditions hold:

• 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 1 prefers 3 over 0, and
- 3 prefers 1 over 2.
Friend 3 is unhappy because:
- 3 is paired with 2, but 3 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:Friends 0 and 1 are both 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 distinct
• pairs.length == n/2
• pairs[i].length == 2
• xi != yi
• 0 <= xi, yi <= n - 1
• Every friend is included in exactly one pair

Approach

#

First, preprocess the input. When querying the preference between two people, we want to provide two people and receive a preference score, but the data supplied by the problem is not convenient for that. We can reorganize it into a two-dimensional array.

# let n = 10;
# let preferences = vec![vec![3]];
let n = n as usize;
let mut pre = vec![vec![0; n]; n];
for i in 0..n {
    for j in 0..(n - 1) {
        pre[i][preferences[i][j] as usize] = n - j - 1;
    }
}

The code above reorganizes preferences into pre. We can then query it conveniently with pre[i][j].

Next, carefully observe the unhappy condition in the example and rewrite it as code: pre[x][u] > pre[x][y] && pre[u][x] > pre[u][v] This expression is interesting. When it holds, not only is x unhappy, but u is unhappy as well.

Looking further, we can see that this expression is completely determined by x and u. Therefore, among the four variables x,y,u,v, there are four such pairs of combinations.

# let (a, b, c, d) = (0, 0, 0, 0);
# let pre = vec![vec![3]];
# let mut set = std::collections::HashSet::new();
if pre[a][c] > pre[a][b] && pre[c][a] > pre[c][d] {
    set.insert(a);
    set.insert(c);
}
if pre[b][c] > pre[b][a] && pre[c][b] > pre[c][d] {
    set.insert(b);
    set.insert(c);
}
if pre[b][d] > pre[b][a] && pre[d][b] > pre[d][c] {
    set.insert(b);
    set.insert(d);
}
if pre[d][a] > pre[d][c] && pre[a][d] > pre[a][b] {
    set.insert(d);
    set.insert(a);
}

Here, set is a hash set used to avoid duplicates. (x,y,u,v are written as a,b,c,d for convenience.)

Finally, iterate over the hash set and return its size.

Rust Code

#

# struct Solution;
impl Solution {
    pub fn unhappy_friends(n: i32, preferences: Vec<Vec<i32>>, pairs: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut pre = vec![vec![0; n]; n];
        for i in 0..n {
            for j in 0..(n - 1) {
                pre[i][preferences[i][j] as usize] = n - j - 1;
            }
        }
        // println!("{:?}", pre);
        use std::collections::*;
        let mut set = HashSet::new();
        for i in 0..pairs.len() {
            for j in 0..pairs.len() {
                let a = pairs[i][0] as usize;
                let b = pairs[i][1] as usize;
                let c = pairs[j][0] as usize;
                let d = pairs[j][1] as usize;
                if pre[a][c] > pre[a][b] && pre[c][a] > pre[c][d] {
                    set.insert(a);
                    set.insert(c);
                }
                if pre[b][c] > pre[b][a] && pre[c][b] > pre[c][d] {
                    set.insert(b);
                    set.insert(c);
                }
                if pre[b][d] > pre[b][a] && pre[d][b] > pre[d][c] {
                    set.insert(b);
                    set.insert(d);
                }
                if pre[d][a] > pre[d][c] && pre[a][d] > pre[a][b] {
                    set.insert(d);
                    set.insert(a);
                }
            }
        }
        set.len() as i32
    }
}