# Minimum Number of People to Teach LeetCode Solution

Difficulty Level Medium
DuolingoViews 561

## Problem Statement

Minimum Number of People to Teach LeetCode Solution- On a social network consisting of `m` users and some friendships between users, two users can communicate with each other if they know a common language.

You are given an integer `n`, an array `languages`, and an array `friendships` where:

• There are `n` languages numbered `1` through `n`,
• `languages[i]` is the set of languages the `i`​​​​​​th​​​​ user knows, and
• `friendships[i] = [u`​​​​​​i`​​​, v`​​​​​​i`]` denotes a friendship between the users `u`​​​​​​​​​​​i​​​​​ and `v`i.

You can choose one language and teach it to some users so that all your friends can communicate with each other. Return the minimum number of users you need to teach.

Note that friendships are not transitive, meaning if `x` is a friend of `y` and `y` is a friend of `z`, this doesn’t guarantee that `x` is a friend of `z`.

```Input: n = 2, languages = [,,[1,2]], friendships = [[1,2],[1,3],[2,3]]
Output: 1
Explanation: You can either teach user 1 the second language or user 2 the first language.```

## Explanation

This sentence is important! “You can choose one language and teach it to some users so that all friends can communicate with each other.”
This should be understood as you can choose only one language to teach to all the people, rather than teaching different languages to different people.

• The key idea is to try each language one by one since we are only allowed to use one language
• Then iterate over each friendship.
• If the two friends can already communicate via a common language, ignore them and move on to the next friendship
• Otherwise, teach them the language (assuming they don’t know it already)
• Find the minimum number of friends to teach any language

## Code

### C++ Code for Minimum Number of People to Teach

```class Solution {
public:

// Memoize results since the same query is asked repeatedly
vector<vector<int>> mem;

// Check to see if u and v already speak a common language
bool check(vector<vector<int>>& a, int u, int v) {
if(mem[u][v] != 0) return mem[u][v] == 1;
for(int i=0; i<a[v].size(); i++) {
if(find(a[u].begin(), a[u].end(), a[v][i]) != a[u].end()) {
mem[v][u] = mem[u][v] = 1;
return true;
}
}
mem[u][v] = mem[v][u] = -1;
return false;
}

int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
int m = languages.size(), ret = m, i;
mem.assign(m + 1, vector<int>(m + 1, 0));

for(i=0; i<m; i++)
sort(languages[i].begin(), languages[i].end()); 		// May not be necessary, just a precaution

for(int lang=1; lang<=n; lang++) {
int count = 0;
vector<bool> teach(m, false);
for(i=0; i<friendships.size(); i++) {
int u = friendships[i] - 1;
int v = friendships[i] - 1;
if(check(languages, u, v))
continue;
if(find(languages[u].begin(), languages[u].end(), lang) == languages[u].end()) {
if(!teach[u])
count++;
teach[u] = true;
}
if(find(languages[v].begin(), languages[v].end(), lang) == languages[v].end()) {
if(!teach[v])
count++;
teach[v] = true;
}
}
ret = min(ret, count);
}
return ret;
}
};```

### Java Code for Minimum Number of People to Teach

```class Solution {
public int minimumTeachings(int n, int[][] languages, int[][] friendships) {

// record the languages known to every user
Map<Integer,Set<Integer>> ul = new HashMap<>();
for(int i=0; i<languages.length; i++) {
Set<Integer> lang = new HashSet<>();
ul.put(i+1, lang);
for(int l : languages[i]) {
}
}

// if two users are friends and they can't speak to each other due to language issue, record it
Map<Integer,Set<Integer>> uf = new HashMap<>();
for(int i=0; i<friendships.length; i++) {
int[] frnd = friendships[i];
boolean canSpk = false;
for(int l : ul.get(frnd)) {
if(ul.get(frnd).contains(l)) {
canSpk = true;
break;
}
}
if(canSpk) continue;

uf.putIfAbsent(frnd,new HashSet<>());
uf.putIfAbsent(frnd,new HashSet<>());
}

int ans = Integer.MAX_VALUE;
// for every language, see how many users need to learn it
for(int i=1; i<=n; i++) {
int tot = 0;
// if we have to teach language i, then how many users need to learn this?
for(int key : uf.keySet()) {
if(!ul.get(key).contains(i)) tot++;
}
// if this language needs to be learned by less number of people, then this is the answer, else don't override the ans
ans = Math.min(ans, tot);
}

return ans;
}
}```

### Python Code for Minimum Number of People to Teach

```class Solution:
def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
languages = [set(l) for l in languages]

dontspeak = set()
for u, v in friendships:
u = u-1
v = v-1
if languages[u] & languages[v]: continue

langcount = Counter()
for f in dontspeak:
for l in languages[f]:
langcount[l] += 1

return 0 if not dontspeak else len(dontspeak) - max(list(langcount.values()))
```

O(M*N)

O(N)

Translate »