You are given an integer n representing the number of people in a social network, where each person is labeled from 1 to n. Each person may know exactly one language, as described by the languages list, where languages[i] is a list of languages known by the ith person. You are also given a list of friendships, where each element is a pair [u, v] that means person u and person v are friends.
Two friends can communicate only if they share at least one common language. Your task is to determine the minimum number of people you must teach a single language so that all friendships can communicate. You may choose any language to teach, and each person can be taught at most one language.
Constraints:
At first glance, it seems you might need to teach as many people as possible to cover all possible friendships, but that's inefficient. Instead, the key is to focus only on the friendships where the two friends cannot communicate (i.e., they have no common language).
For each such "problematic" friendship, you need to make at least one of the two people learn a new language so that they can communicate. However, since you can choose which language to teach, you want to minimize the total number of people taught by picking the language that covers the most "problematic" people.
The brute-force approach would be to try teaching every possible language to all problematic people and count how many people need to learn it. The optimized idea is to focus on the language that is already known by the most problematic people, so you teach the rest of the problematic people that language.
[u, v].languages[u] and languages[v] have any intersection.u and v to a set of "problematic" people.By focusing only on problematic people and maximizing the reuse of existing language knowledge, you minimize the number of teachings.
Input:
n = 3
languages = [[1], [2], [3]]
friendships = [[1,2],[2,3],[1,3]]
Step 1: Identify Problematic Friendships
- (1,2): Person 1 knows [1], Person 2 knows [2]. No overlap. Both are problematic.
- (2,3): [2] vs [3]. No overlap. Both are problematic.
- (1,3): [1] vs [3]. No overlap. Both are problematic.
Problematic people: {1,2,3}
Step 2: Language Coverage
- Language 1: Only person 1 knows it.
- Language 2: Only person 2 knows it.
- Language 3: Only person 3 knows it.
Step 3: Minimum to Teach
- If we pick language 1: Teach to 2 and 3 (2 people).
- If we pick language 2: Teach to 1 and 3 (2 people).
- If we pick language 3: Teach to 1 and 2 (2 people).
Answer: 2
Brute-force:
- For each language, for each problematic person, check if they know it.
- Complexity: O(L * P), where L is the number of languages and P is the number of problematic people.
Optimized Approach:
- Identifying problematic friendships: O(F * K), where F is the number of friendships and K is the average number of languages per person.
- Counting language coverage: O(P * K), where P is the number of problematic people.
- Final pass over languages: O(L).
- Total: O(F * K + P * K + L)
Space: O(N * K) for storing language sets, plus O(P) for problematic people, and O(L) for language counts.
The key insight is to focus only on friendships where communication is not possible, and only on the people involved in those friendships. By choosing the language that is already most common among these problematic people, you minimize the number of teachings required. This approach is efficient and leverages hash maps and set operations for fast lookups, making it both practical and elegant.
class Solution:
def minimumTeachings(self, n, languages, friendships):
# Convert to 0-based index for easier handling
lang_sets = [set(langs) for langs in languages]
problematic = set()
for u, v in friendships:
u -= 1; v -= 1
if not (lang_sets[u] & lang_sets[v]):
problematic.add(u)
problematic.add(v)
if not problematic:
return 0
# Count for each language how many problematic people already know it
from collections import Counter
lang_count = Counter()
for person in problematic:
for lang in lang_sets[person]:
lang_count[lang] += 1
# For each language, compute how many problematic people do NOT know it
min_teach = float('inf')
for lang in range(1, n+1):
teach = len(problematic) - lang_count.get(lang, 0)
min_teach = min(min_teach, teach)
return min_teach
class Solution {
public:
int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
int m = languages.size();
vector<unordered_set<int>> lang_sets(m);
for (int i = 0; i < m; ++i) {
for (int l : languages[i]) lang_sets[i].insert(l);
}
unordered_set<int> problematic;
for (auto& f : friendships) {
int u = f[0] - 1, v = f[1] - 1;
bool can_communicate = false;
for (int l : lang_sets[u]) {
if (lang_sets[v].count(l)) {
can_communicate = true;
break;
}
}
if (!can_communicate) {
problematic.insert(u);
problematic.insert(v);
}
}
if (problematic.empty()) return 0;
vector<int> lang_count(n+1, 0);
for (int person : problematic) {
for (int l : lang_sets[person]) {
lang_count[l]++;
}
}
int min_teach = problematic.size();
for (int lang = 1; lang <= n; ++lang) {
min_teach = min(min_teach, (int)problematic.size() - lang_count[lang]);
}
return min_teach;
}
};
class Solution {
public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
int m = languages.length;
List<Set<Integer>> langSets = new ArrayList<>();
for (int[] langs : languages) {
Set<Integer> set = new HashSet<>();
for (int l : langs) set.add(l);
langSets.add(set);
}
Set<Integer> problematic = new HashSet<>();
for (int[] f : friendships) {
int u = f[0] - 1, v = f[1] - 1;
Set<Integer> setU = langSets.get(u), setV = langSets.get(v);
boolean canCommunicate = false;
for (int l : setU) {
if (setV.contains(l)) {
canCommunicate = true;
break;
}
}
if (!canCommunicate) {
problematic.add(u);
problematic.add(v);
}
}
if (problematic.isEmpty()) return 0;
int[] langCount = new int[n+1];
for (int person : problematic) {
for (int l : langSets.get(person)) {
langCount[l]++;
}
}
int minTeach = problematic.size();
for (int lang = 1; lang <= n; ++lang) {
minTeach = Math.min(minTeach, problematic.size() - langCount[lang]);
}
return minTeach;
}
}
var minimumTeachings = function(n, languages, friendships) {
const langSets = languages.map(langs => new Set(langs));
const problematic = new Set();
for (const [u, v] of friendships) {
const u0 = u - 1, v0 = v - 1;
let canCommunicate = false;
for (const l of langSets[u0]) {
if (langSets[v0].has(l)) {
canCommunicate = true;
break;
}
}
if (!canCommunicate) {
problematic.add(u0);
problematic.add(v0);
}
}
if (problematic.size === 0) return 0;
const langCount = new Array(n+1).fill(0);
for (const person of problematic) {
for (const l of langSets[person]) {
langCount[l]++;
}
}
let minTeach = problematic.size;
for (let lang = 1; lang <= n; ++lang) {
minTeach = Math.min(minTeach, problematic.size - langCount[lang]);
}
return minTeach;
};