1733. Minimum Number of People to Teach LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1733. Minimum Number of People to Teach LeetCode Solution with the best time and space complexity. The solution to Minimum Number of People to Teach problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Number of People to Teach solution in C++
Minimum Number of People to Teach solution in Java
Minimum Number of People to Teach solution in Python
Additional Resources

1733. Minimum Number of People to Teach LeetCode Solution image

Problem Statement of Minimum Number of People to Teach

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 ith user knows, and
friendships[i] = [ui, vi] denotes a friendship between the users ui 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 <= ui < vi <= languages.length
1 <= friendships.length <= 500
All tuples (ui, vi) are unique
languages[i] contains only unique values

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(m + n)

1733. Minimum Number of People to Teach LeetCode Solution in C++

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].contains(language))
        return false;
    return true;
  }
};
/* code provided by PROGIEZ */

1733. Minimum Number of People to Teach LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

1733. Minimum Number of People to Teach LeetCode Solution in Python

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)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents