-
Notifications
You must be signed in to change notification settings - Fork 2
/
CountUnhappyFriends.java
114 lines (105 loc) · 3.75 KB
/
CountUnhappyFriends.java
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
package Leetcode;
import java.util.HashMap;
import java.util.Map;
/**
* @author kalpak
*
* 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.
*
*/
public class CountUnhappyFriends {
public static int unhappyFriends(int n, int[][] preferences, int[][] pairs) {
Map<Integer, Integer> mapPairs = new HashMap<>();
buildHashMap(pairs, mapPairs);
int count = 0;
for(int[] pair : pairs) {
// Check both the people in the pair
count += isUnhappy(pair[0], pair[1], preferences, mapPairs);
count += isUnhappy(pair[1], pair[0], preferences, mapPairs);
}
return count;
}
private static int isUnhappy(int person, int personsPair, int[][] preferences, Map<Integer, Integer> mapPairs) {
for(int personsPreference : preferences[person]) {
if(personsPreference == personsPair)
return 0; // Happy
// Now check for unhappiness
// person prefers personsPreference over personsPair
// check if personsPreference prefers person over its own pair
int pairOfPersonsPreference = mapPairs.get(personsPreference);
for(int mate : preferences[personsPreference]) {
if(mate == person)
return 1; // Yes, we have unhappy friends
else if (mate == pairOfPersonsPreference)
break; // They are happy
}
}
return 0;
}
//helper to build bijection mapping
private static void buildHashMap(int[][] pairs, Map<Integer, Integer> map){
for(int[] pair : pairs){
map.put(pair[0],pair[1]);
map.put(pair[1],pair[0]);
}
}
public static void main(String[] args) {
int[][] preferences = new int[][]{{1, 2, 3}, {3, 2, 0}, {3, 1, 0}, {1, 2, 0}};
int[][] pairs = new int[][]{{0, 1}, {2, 3}};
System.out.println("The number of unhappy friends: " + unhappyFriends(4, preferences, pairs));
}
}