Skip to content

1733. Minimum Number of People to Teach 👎

  • Time: $O(mn)$
  • Space: $O(m + n)$
 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
class Solution {
 public:
  int minimumTeachings(int n, vector<vector<int>>& languages,
                       vector<vector<int>>& friendships) {
    vector<unordered_set<int>> languageSets;
    unordered_set<int> needTeach;
    unordered_map<int, int> languageCount;

    for (const vector<int>& language : languages)
      languageSets.push_back({language.begin(), language.end()});

    // Find friends that can't communicate.
    for (const vector<int>& friendship : friendships) {
      const int u = friendship[0] - 1;
      const int v = friendship[1] - 1;
      if (cantTalk(languageSets, u, v)) {
        needTeach.insert(u);
        needTeach.insert(v);
      }
    }

    // Find the most popular language.
    for (const int u : needTeach)
      for (const int language : languageSets[u])
        ++languageCount[language];

    // Teach the most popular language to people who don't understand.
    int maxCount = 0;
    for (const auto& [_, freq] : languageCount)
      maxCount = max(maxCount, freq);

    return needTeach.size() - maxCount;
  }

 private:
  // Returns true if u can't talk with v.
  bool cantTalk(const vector<unordered_set<int>>& languageSets, int u, int v) {
    for (const int language : languageSets[u])
      if (languageSets[v].count(language))
        return false;
    return true;
  }
};

 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
class Solution {
  public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
    List<Set<Integer>> languageSets = new ArrayList<>();
    Set<Integer> needTeach = new HashSet<>();
    Map<Integer, Integer> languageCount = new HashMap<>();

    for (int[] language : languages)
      languageSets.add(new HashSet<>(Arrays.stream(language).boxed().toList()));

    // Find friends that can't communicate.
    for (int[] friendship : friendships) {
      final int u = friendship[0] - 1;
      final int v = friendship[1] - 1;
      if (cantTalk(languageSets, u, v)) {
        needTeach.add(u);
        needTeach.add(v);
      }
    }

    // Find the most popular language.
    for (int u : needTeach)
      for (final int language : languageSets.get(u))
        languageCount.merge(language, 1, Integer::sum);

    // Teach the most popular language to people who don't understand.
    int maxCount = 0;
    for (int freq : languageCount.values())
      maxCount = Math.max(maxCount, freq);

    return needTeach.size() - maxCount;
  }

  // Returns true if u can't talk with v.
  private boolean cantTalk(List<Set<Integer>> languageSets, int u, int v) {
    for (int language : languageSets.get(u))
      if (languageSets.get(v).contains(language))
        return false;
    return true;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
    languageSets = [set(languages) for languages in languages]
    needTeach = set()
    languageCount = collections.Counter()

    # Find friends that can't communicate.
    for u, v in friendships:
      if not languageSets[u - 1] & languageSets[v - 1]:
        needTeach.add(u - 1)
        needTeach.add(v - 1)

    # Find the most popular language.
    for u in needTeach:
      for language in languageSets[u]:
        languageCount[language] += 1

    # Teach the most popular language to people don't understand.
    return len(needTeach) - max(languageCount.values(), default=0)