# Minimum Number of People to Teach
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-number-of-people-to-teach)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-people-to-teach
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Hash Table
**Companies:** [Duolingo](https://scaleengineer.com/companies/duolingo)
---
## Problem
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 `vi`.

You can choose **one** language and teach it to some users so that all 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`. 

**Example 1:**

**Input:** n = 2, languages = [[1],[2],[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.

**Example 2:**

**Input:** n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
**Output:** 2
**Explanation:** Teach the third language to users 1 and 3, yielding two users to teach.

**Constraints:**

* `2 <= n <= 500`
* `languages.length == m`
* `1 <= m <= 500`
* `1 <= languages[i].length <= n`
* `1 <= languages[i][j] <= n`
* `1 <= u​​​​​​i < v​​​​​​i <= languages.length`
* `1 <= friendships.length <= 500`
* All tuples `(u​​​​​i, v​​​​​​i)` are unique
* `languages[i]` contains only unique values

# Approaches
## Brute-Force Check for Each Language
This approach iterates through every possible language from 1 to `n` that we could teach. For each candidate language, it determines the number of users that would need to be taught this language to satisfy all friendship communication requirements. The minimum count across all languages is the answer.
**Time:** O(n * F * L), where `n` is the number of languages, `F` is the number of friendships, and `L` is the maximum number of languages a user knows. We iterate through `n` languages. For each, we iterate through `F` friendships. The `canCommunicate` check takes `O(L)` time with pre-processed sets. · **Space:** O(m * L + m), where `m` is the number of users and `L` is the maximum number of languages a user knows. `O(m*L)` space is used to store the language sets for each user, and the `usersToTeach` set can hold at most `m` users.
**Pros:** The logic is straightforward and directly models the problem of trying each possible language.
**Cons:** This approach is inefficient because it repeatedly calculates which friendships are 'disconnected' for each of the `n` languages. This leads to a higher time complexity.
### Explanation
The algorithm iterates through each language `l` from `1` to `n`. For each `l`, we calculate the number of people to teach. We initialize a set, `usersToTeach`, to keep track of them to avoid duplicates. We then iterate through every friendship `[u, v]`. For each friendship, we first check if users `u` and `v` can already communicate. This is done by checking if their sets of known languages have a non-empty intersection. If they cannot communicate, they form a 'disconnected pair'. For this pair to communicate using language `l`, both must know it. We check if user `u` already knows language `l`. If not, we add `u` to our `usersToTeach` set for language `l`. We do the same for user `v`. After checking all friendships, the size of the `usersToTeach` set gives the total number of teachings required for language `l`. We keep track of the minimum size found so far across all languages. Finally, after checking all `n` languages, we return the overall minimum.

To make language lookups efficient, we first convert the input `languages` array into an array of `HashSet`s.

```java
class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int m = languages.length;
        // Convert languages to Sets for easier lookup
        Set<Integer>[] langSets = new HashSet[m + 1];
        for (int i = 1; i <= m; i++) {
            langSets[i] = new HashSet<>();
            for (int lang : languages[i - 1]) {
                langSets[i].add(lang);
            }
        }

        int minTeachings = m; // Maximum possible teachings is m

        for (int l = 1; l <= n; l++) {
            Set<Integer> usersToTeach = new HashSet<>();
            for (int[] friendship : friendships) {
                int u = friendship[0];
                int v = friendship[1];

                if (!canCommunicate(langSets, u, v)) {
                    if (!langSets[u].contains(l)) {
                        usersToTeach.add(u);
                    }
                    if (!langSets[v].contains(l)) {
                        usersToTeach.add(v);
                    }
                }
            }
            minTeachings = Math.min(minTeachings, usersToTeach.size());
        }
        return minTeachings;
    }

    private boolean canCommunicate(Set<Integer>[] langSets, int u, int v) {
        Set<Integer> langU = langSets[u];
        Set<Integer> langV = langSets[v];
        // Iterate over the smaller set for efficiency
        if (langU.size() > langV.size()) {
            Set<Integer> temp = langU;
            langU = langV;
            langV = temp;
        }
        for (int lang : langU) {
            if (langV.contains(lang)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Initialize `minTeachings` to a very large value (e.g., the total number of users).
- For each language `l` from `1` to `n`:
  - Create an empty set `usersToTeachForL` to store unique users who need to be taught language `l`.
  - For each friendship `[u, v]`:
    - Check if users `u` and `v` share a common language. This check itself can be done by iterating through the languages of one user and checking for existence in the other's language list.
    - If they do not share a common language:
      - Check if user `u` already knows language `l`. If not, add `u` to the `usersToTeachForL` set.
      - Check if user `v` already knows language `l`. If not, add `v` to the `usersToTeachForL` set.
  - After checking all friendships, the size of the `usersToTeachForL` set is the number of teachings required for language `l`.
  - Update `minTeachings = min(minTeachings, usersToTeachForL.size())`.
- Return `minTeachings`.

## Optimized Approach by Identifying Disconnected Users First
This approach improves upon the brute-force method by first identifying the core problem: we only need to teach users who are part of at least one 'disconnected' friendship (where the two friends share no common language). By first finding this set of users, we can then find the best language to teach them, avoiding redundant checks.
**Time:** O(m*L + F*L), where `m` is users, `F` is friendships, and `L` is max languages/user. This consists of `O(m*L)` to build language sets, `O(F*L)` to find disconnected users, and `O(|disconnectedUsers| * L)` (at most `O(m*L)`) to count frequencies. · **Space:** O(m * L + n), where `m` is the number of users, `L` is the max languages per user, and `n` is the number of languages. `O(m*L)` for language sets, `O(m)` for the `disconnectedUsers` set, and `O(n)` for the frequency count array.
**Pros:** Highly efficient as it avoids redundant computations by identifying the set of relevant users only once.; The time complexity is significantly better than the brute-force approach, making it suitable for larger constraints.
**Cons:** The logic is slightly more complex, involving multiple steps and data structures (sets, frequency arrays).
### Explanation
The key insight is that any user who can already communicate with all their friends doesn't need to be taught a new language. The problem is confined to users in friendships that lack a common language.

**Step 1: Identify Disconnected Users.** We iterate through all friendships once. For each friendship `[u, v]`, we check if they can communicate. If not, we add both `u` and `v` to a set called `disconnectedUsers`. This set now contains all users who are part of at least one communication problem. If this set is empty after checking all friendships, it means everyone can communicate, and the answer is 0.

**Step 2: Find the Most Common Language.** The goal is to teach a single language `l` to the users in `disconnectedUsers` who don't already know it. The number of people to teach for a language `l` is `|disconnectedUsers| - (number of users in disconnectedUsers who already know l)`. To minimize this value, we need to maximize the number of users in `disconnectedUsers` who already know a common language. So, we find which language is most prevalent among the `disconnectedUsers`. We can use a frequency map (or an array) to count how many users in `disconnectedUsers` know each language.

**Step 3: Calculate the Result.** We find the maximum frequency `maxFreq` from our frequency map. This `maxFreq` represents the largest group of users within `disconnectedUsers` that we *don't* have to teach, if we pick their common language. The minimum number of users to teach is therefore the total number of disconnected users minus this maximum frequency: `disconnectedUsers.size() - maxFreq`.

```java
class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int m = languages.length;
        Set<Integer>[] langSets = new HashSet[m + 1];
        for (int i = 1; i <= m; i++) {
            langSets[i] = new HashSet<>();
            for (int lang : languages[i - 1]) {
                langSets[i].add(lang);
            }
        }

        Set<Integer> disconnectedUsers = new HashSet<>();
        for (int[] friendship : friendships) {
            int u = friendship[0];
            int v = friendship[1];
            if (!canCommunicate(langSets, u, v)) {
                disconnectedUsers.add(u);
                disconnectedUsers.add(v);
            }
        }

        if (disconnectedUsers.isEmpty()) {
            return 0;
        }

        int[] langFrequency = new int[n + 1];
        int maxFreq = 0;
        for (int user : disconnectedUsers) {
            for (int lang : langSets[user]) {
                langFrequency[lang]++;
                maxFreq = Math.max(maxFreq, langFrequency[lang]);
            }
        }

        return disconnectedUsers.size() - maxFreq;
    }

    private boolean canCommunicate(Set<Integer>[] langSets, int u, int v) {
        Set<Integer> langU = langSets[u];
        Set<Integer> langV = langSets[v];
        if (langU.size() > langV.size()) {
            Set<Integer> temp = langU;
            langU = langV;
            langV = temp;
        }
        for (int lang : langU) {
            if (langV.contains(lang)) {
                return true;
            }
        }
        return false;
    }
}
```
### Algorithm
- Pre-process the `languages` array into a more efficient data structure, like an array of `HashSet`s, for quick language lookups for each user.
- Create an empty set `disconnectedUsers`.
- Iterate through each friendship `[u, v]`:
  - Check if `u` and `v` share a common language.
  - If they don't, add both `u` and `v` to `disconnectedUsers`.
- If `disconnectedUsers` is empty, it means all friends can communicate, so return 0.
- Create a frequency array `langCounts` of size `n+1`, initialized to zeros.
- For each `user` in `disconnectedUsers`:
  - For each `language` that `user` knows:
    - Increment `langCounts[language]`.
- Find the maximum value `maxFreq` in `langCounts`.
- The result is `disconnectedUsers.size() - maxFreq`.

# Solutions
### Java

```java
class Solution {
public
  int minimumTeachings(int n, int[][] languages, int[][] friendships) {
    Set<Integer> s = new HashSet<>();
    for (var e : friendships) {
      int u = e[0], v = e[1];
      if (!check(u, v, languages)) {
        s.add(u);
        s.add(v);
      }
    }
    if (s.isEmpty()) {
      return 0;
    }
    int[] cnt = new int[n + 1];
    for (int u : s) {
      for (int l : languages[u - 1]) {
        ++cnt[l];
      }
    }
    int mx = 0;
    for (int v : cnt) {
      mx = Math.max(mx, v);
    }
    return s.size() - mx;
  }
private
  boolean check(int u, int v, int[][] languages) {
    for (int x : languages[u - 1]) {
      for (int y : languages[v - 1]) {
        if (x == y) {
          return true;
        }
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumTeachings(int n, vector<vector<int>> &languages,
                       vector<vector<int>> &friendships) {
    unordered_set<int> s;
    for (auto &e : friendships) {
      int u = e[0], v = e[1];
      if (!check(u, v, languages)) {
        s.insert(u);
        s.insert(v);
      }
    }
    if (s.empty()) {
      return 0;
    }
    vector<int> cnt(n + 1);
    for (int u : s) {
      for (int &l : languages[u - 1]) {
        ++cnt[l];
      }
    }
    return s.size() - *max_element(cnt.begin(), cnt.end());
  }
  bool check(int u, int v, vector<vector<int>> &languages) {
    for (int x : languages[u - 1]) {
      for (int y : languages[v - 1]) {
        if (x == y) {
          return true;
        }
      }
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int: def check(u, v): for x in languages[u - 1]: for y in languages[v - 1]: if x == y: return True return False s = set() for u, v in friendships: if not check(u, v): s . add(u) s . add(v) cnt = Counter() for u in s: for l in languages[u - 1]: cnt[l] += 1 return len(s) - max(cnt . values(), default=0)

```