Minimum Number of People to Teach

Med

#1587Time: 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.1 company

Patterns

Greedy

Data structures

Array Hash Table

Companies

Duolingo

Prompt

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 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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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 HashSets.

1class Solution {2    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {3        int m = languages.length;4        // Convert languages to Sets for easier lookup5        Set<Integer>[] langSets = new HashSet[m + 1];6        for (int i = 1; i <= m; i++) {7            langSets[i] = new HashSet<>();8            for (int lang : languages[i - 1]) {9                langSets[i].add(lang);10            }11        }12 13        int minTeachings = m; // Maximum possible teachings is m14 15        for (int l = 1; l <= n; l++) {16            Set<Integer> usersToTeach = new HashSet<>();17            for (int[] friendship : friendships) {18                int u = friendship[0];19                int v = friendship[1];20 21                if (!canCommunicate(langSets, u, v)) {22                    if (!langSets[u].contains(l)) {23                        usersToTeach.add(u);24                    }25                    if (!langSets[v].contains(l)) {26                        usersToTeach.add(v);27                    }28                }29            }30            minTeachings = Math.min(minTeachings, usersToTeach.size());31        }32        return minTeachings;33    }34 35    private boolean canCommunicate(Set<Integer>[] langSets, int u, int v) {36        Set<Integer> langU = langSets[u];37        Set<Integer> langV = langSets[v];38        // Iterate over the smaller set for efficiency39        if (langU.size() > langV.size()) {40            Set<Integer> temp = langU;41            langU = langV;42            langV = temp;43        }44        for (int lang : langU) {45            if (langV.contains(lang)) {46                return true;47            }48        }49        return false;50    }51}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Pre-process the languages array into a more efficient data structure, like an array of HashSets, 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.

Walkthrough

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.

1class Solution {2    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {3        int m = languages.length;4        Set<Integer>[] langSets = new HashSet[m + 1];5        for (int i = 1; i <= m; i++) {6            langSets[i] = new HashSet<>();7            for (int lang : languages[i - 1]) {8                langSets[i].add(lang);9            }10        }11 12        Set<Integer> disconnectedUsers = new HashSet<>();13        for (int[] friendship : friendships) {14            int u = friendship[0];15            int v = friendship[1];16            if (!canCommunicate(langSets, u, v)) {17                disconnectedUsers.add(u);18                disconnectedUsers.add(v);19            }20        }21 22        if (disconnectedUsers.isEmpty()) {23            return 0;24        }25 26        int[] langFrequency = new int[n + 1];27        int maxFreq = 0;28        for (int user : disconnectedUsers) {29            for (int lang : langSets[user]) {30                langFrequency[lang]++;31                maxFreq = Math.max(maxFreq, langFrequency[lang]);32            }33        }34 35        return disconnectedUsers.size() - maxFreq;36    }37 38    private boolean canCommunicate(Set<Integer>[] langSets, int u, int v) {39        Set<Integer> langU = langSets[u];40        Set<Integer> langV = langSets[v];41        if (langU.size() > langV.size()) {42            Set<Integer> temp = langU;43            langU = langV;44            langV = temp;45        }46        for (int lang : langU) {47            if (langV.contains(lang)) {48                return true;49            }50        }51        return false;52    }53}

Complexity

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.

Trade-offs

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).

Solutions

Solution

1class Solution {2public3  int minimumTeachings(int n, int[][] languages, int[][] friendships) {4    Set<Integer> s = new HashSet<>();5    for (var e : friendships) {6      int u = e[0], v = e[1];7      if (!check(u, v, languages)) {8        s.add(u);9        s.add(v);10      }11    }12    if (s.isEmpty()) {13      return 0;14    }15    int[] cnt = new int[n + 1];16    for (int u : s) {17      for (int l : languages[u - 1]) {18        ++cnt[l];19      }20    }21    int mx = 0;22    for (int v : cnt) {23      mx = Math.max(mx, v);24    }25    return s.size() - mx;26  }27private28  boolean check(int u, int v, int[][] languages) {29    for (int x : languages[u - 1]) {30      for (int y : languages[v - 1]) {31        if (x == y) {32          return true;33        }34      }35    }36    return false;37  }38}

1class Solution {2public:3  int minimumTeachings(int n, vector<vector<int>> &languages,4                       vector<vector<int>> &friendships) {5    unordered_set<int> s;6    for (auto &e : friendships) {7      int u = e[0], v = e[1];8      if (!check(u, v, languages)) {9        s.insert(u);10        s.insert(v);11      }12    }13    if (s.empty()) {14      return 0;15    }16    vector<int> cnt(n + 1);17    for (int u : s) {18      for (int &l : languages[u - 1]) {19        ++cnt[l];20      }21    }22    return s.size() - *max_element(cnt.begin(), cnt.end());23  }24  bool check(int u, int v, vector<vector<int>> &languages) {25    for (int x : languages[u - 1]) {26      for (int y : languages[v - 1]) {27        if (x == y) {28          return true;29        }30      }31    }32    return false;33  }34};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem