Skip to content

1583. Count Unhappy Friends

Description

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.

Solutions

Solution 1: Enumeration

Thinking

After pairing, \(x\) is unhappy if some \(u\) is preferred to \(x\)'s partner and \(u\) also prefers \(x\) to \(u\)'s partner. \(n\le 500\), so we may scan each \(x\) and those better-liked friends.

Build a closeness map and a partner table. For each \(x\), inspect only friends ranked above partner \(y\). The first \(u\) who ranks \(x\) above \(u\)'s own partner makes \(x\) unhappy, and the inner loop can stop.

We use an array \(\textit{d}\) to record the closeness between each pair of friends, where \(\textit{d}[i][j]\) represents the closeness of friend \(i\) to friend \(j\) (the smaller the value, the closer they are). Additionally, we use an array \(\textit{p}\) to record the paired friend for each friend.

We enumerate each friend \(x\). For \(x\)'s paired friend \(y\), we find the closeness \(\textit{d}[x][y]\) of \(x\) to \(y\). Then, we enumerate other friends \(u\) who are closer than \(\textit{d}[x][y]\). If there exists a friend \(u\) such that the closeness \(\textit{d}[u][x]\) of \(u\) to \(x\) is higher than \(\textit{d}[u][y]\), then \(x\) is an unhappy friend, and we increment the result by one.

After the enumeration, we obtain the number of unhappy friends.

The time complexity is \(O(n^2)\), and the space complexity is \(O(n^2)\). Here, \(n\) is the number of friends.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def unhappyFriends(
        self, n: int, preferences: List[List[int]], pairs: List[List[int]]
    ) -> int:
        d = [{x: j for j, x in enumerate(p)} for p in preferences]
        p = {}
        for x, y in pairs:
            p[x] = y
            p[y] = x
        ans = 0
        for x in range(n):
            y = p[x]
            for i in range(d[x][y]):
                u = preferences[x][i]
                v = p[u]
                if d[u][x] < d[u][v]:
                    ans += 1
                    break
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
        int[][] d = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n - 1; ++j) {
                d[i][preferences[i][j]] = j;
            }
        }
        int[] p = new int[n];
        for (var e : pairs) {
            int x = e[0], y = e[1];
            p[x] = y;
            p[y] = x;
        }
        int ans = 0;
        for (int x = 0; x < n; ++x) {
            int y = p[x];
            for (int i = 0; i < d[x][y]; ++i) {
                int u = preferences[x][i];
                int v = p[u];
                if (d[u][x] < d[u][v]) {
                    ++ans;
                    break;
                }
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int unhappyFriends(int n, vector<vector<int>>& preferences, vector<vector<int>>& pairs) {
        vector<vector<int>> d(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n - 1; ++j) {
                d[i][preferences[i][j]] = j;
            }
        }
        vector<int> p(n, 0);
        for (auto& e : pairs) {
            int x = e[0], y = e[1];
            p[x] = y;
            p[y] = x;
        }
        int ans = 0;
        for (int x = 0; x < n; ++x) {
            int y = p[x];
            for (int i = 0; i < d[x][y]; ++i) {
                int u = preferences[x][i];
                int v = p[u];
                if (d[u][x] < d[u][v]) {
                    ++ans;
                    break;
                }
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
func unhappyFriends(n int, preferences [][]int, pairs [][]int) (ans int) {
    d := make([][]int, n)
    for i := range d {
        d[i] = make([]int, n)
    }

    for i := 0; i < n; i++ {
        for j := 0; j < n-1; j++ {
            d[i][preferences[i][j]] = j
        }
    }

    p := make([]int, n)
    for _, e := range pairs {
        x, y := e[0], e[1]
        p[x] = y
        p[y] = x
    }

    for x := 0; x < n; x++ {
        y := p[x]
        for i := 0; i < d[x][y]; i++ {
            u := preferences[x][i]
            v := p[u]
            if d[u][x] < d[u][v] {
                ans++
                break
            }
        }
    }

    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function unhappyFriends(n: number, preferences: number[][], pairs: number[][]): number {
    const d: number[][] = Array.from({ length: n }, () => Array(n).fill(0));
    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < n - 1; ++j) {
            d[i][preferences[i][j]] = j;
        }
    }
    const p: number[] = Array(n).fill(0);
    for (const [x, y] of pairs) {
        p[x] = y;
        p[y] = x;
    }
    let ans = 0;
    for (let x = 0; x < n; ++x) {
        const y = p[x];
        for (let i = 0; i < d[x][y]; ++i) {
            const u = preferences[x][i];
            const v = p[u];
            if (d[u][x] < d[u][v]) {
                ++ans;
                break;
            }
        }
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
impl Solution {
    pub fn unhappy_friends(n: i32, preferences: Vec<Vec<i32>>, pairs: Vec<Vec<i32>>) -> i32 {
        let n = n as usize;
        let mut d = vec![vec![0usize; n]; n];
        for i in 0..n {
            for j in 0..(n - 1) {
                let friend = preferences[i][j] as usize;
                d[i][friend] = j;
            }
        }

        let mut p = vec![0usize; n];
        for e in pairs {
            let x = e[0] as usize;
            let y = e[1] as usize;
            p[x] = y;
            p[y] = x;
        }

        let mut ans = 0;

        for x in 0..n {
            let y = p[x];
            for i in 0..d[x][y] {
                let u = preferences[x][i] as usize;
                let v = p[u];
                if d[u][x] < d[u][v] {
                    ans += 1;
                    break;
                }
            }
        }

        ans
    }
}

Comments