LeetCode 1733 - Minimum Number of People to Teach
This problem models communication in a social network where each user knows one or more languages. Two users can communicate directly if they share at least one common language.
Difficulty: 🟡 Medium
Topics: Array, Hash Table, Greedy
Solution
Problem Understanding
This problem models communication in a social network where each user knows one or more languages. Two users can communicate directly if they share at least one common language. The goal is to ensure that every friendship pair can communicate after teaching exactly one chosen language to some users.
The input consists of three parts:
n, the total number of possible languages.languages, wherelanguages[i]contains the languages known by useri + 1.friendships, where each pair[u, v]represents a friendship between usersuandv.
The important detail is that communication is only checked for direct friendships. Communication is not transitive. Even if user A can talk to B and B can talk to C, that does not imply A can talk to C.
We are allowed to pick one language and teach it to any number of users. After teaching, every friendship pair must share at least one common language. We want to minimize the number of users taught.
The constraints are relatively small:
- At most 500 users
- At most 500 friendships
- At most 500 languages
These bounds suggest that solutions involving nested loops over users and languages are acceptable. A carefully designed brute-force approach may already pass, but we can still optimize the logic significantly.
Several edge cases are important:
- Some friendship pairs may already communicate, meaning they require no action.
- Multiple disconnected friendship pairs may require teaching.
- A user may already know the chosen teaching language and therefore should not be counted.
- There may be no problematic friendships at all, in which case the answer is
0. - A naive implementation could mistakenly count users multiple times across different friendships.
The core challenge is identifying which users actually need teaching for a given candidate language.
Approaches
Brute Force Approach
A straightforward brute-force solution would try every possible language from 1 to n. For each language, we examine every friendship pair.
If two friends already share a language, nothing needs to be done. Otherwise, at least one of them must learn the chosen language. We could simulate this process by collecting all users involved in problematic friendships who do not already know the candidate language.
After processing all friendships, the number of collected users represents how many people must learn that language. We repeat this for every language and take the minimum.
This approach is correct because we explicitly test every possible language choice and compute the exact number of users that must be taught.
The brute-force idea is already efficient enough for the given constraints, but the key optimization is realizing that we only care about users involved in friendships that currently cannot communicate.
Key Insight
The most important observation is that friendships that already share a common language are irrelevant. No teaching is required for them regardless of which language we choose.
Therefore, we first identify all "problematic" friendship pairs, meaning pairs with no shared language.
Once we know the problematic users, the problem becomes:
Choose one language that is already known by as many problematic users as possible.
If we choose language L, then every problematic user who already knows L needs no teaching. Everyone else must learn it.
So instead of simulating teaching independently for every friendship, we can:
- Collect all users participating in problematic friendships.
- Count how many of these users already know each language.
- Choose the language with the maximum count.
- Teach the remaining problematic users.
This transforms the problem into a frequency counting problem.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n × f × k) | O(m) | Tries every language and processes all friendships directly |
| Optimal | O(f × k + m × k) | O(m + n) | Focuses only on problematic friendships and counts language frequencies |
Where:
f= number of friendshipsm= number of usersk= average number of languages per user
Algorithm Walkthrough
- Convert each user's language list into a set.
Using sets allows efficient membership testing and intersection checks. Since we repeatedly need to determine whether two users share a language, sets make this operation much faster and cleaner. 2. Iterate through every friendship pair.
For each friendship [u, v], retrieve the language sets for both users.
3. Check whether the two users already share a common language.
We can test this by checking whether the intersection of the two sets is non-empty.
If they already share a language, no action is required. 4. Collect users from problematic friendships.
If the two users cannot communicate, add both users into a set called need_teaching.
We use a set because the same user may appear in multiple problematic friendships, but we only want to count them once. 5. Count language frequencies among problematic users.
For every user in need_teaching, count how many users already know each language.
This tells us how many users would not require teaching if we selected that language. 6. Find the language known by the maximum number of problematic users.
Suppose the best language is already known by best_count users.
7. Compute the answer.
Every problematic user who does not already know the chosen language must learn it.
Therefore:
answer = len(need_teaching) - best_count
Why it works
Every problematic friendship must eventually share at least one common language. Since we are restricted to teaching only one language globally, all unresolved users must converge toward the same language.
For a chosen language L, the only users needing instruction are problematic users who do not already know L. Therefore, minimizing teachings is equivalent to maximizing how many problematic users already know the chosen language.
Because the algorithm evaluates all languages implicitly through frequency counting, it always finds the optimal answer.
Python Solution
from typing import List
from collections import defaultdict
class Solution:
def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
language_sets = [set(lang_list) for lang_list in languages]
need_teaching = set()
for u, v in friendships:
user_u_languages = language_sets[u - 1]
user_v_languages = language_sets[v - 1]
if user_u_languages.isdisjoint(user_v_languages):
need_teaching.add(u - 1)
need_teaching.add(v - 1)
language_count = defaultdict(int)
for user in need_teaching:
for language in language_sets[user]:
language_count[language] += 1
max_known = 0
for count in language_count.values():
max_known = max(max_known, count)
return len(need_teaching) - max_known
The implementation begins by converting every user's language list into a set. This is important because checking whether two users share a language becomes efficient with set operations.
Next, we iterate through every friendship pair. The isdisjoint() method checks whether two sets have no common elements. If two users cannot communicate, both users are added to the need_teaching set.
The need_teaching set contains exactly the users who participate in at least one unresolved friendship. Users outside this set never require teaching because all their friendships already work.
After identifying problematic users, we count language frequencies. For each user in need_teaching, we increment the count for every language they already know.
The language with the highest frequency is the best teaching language because it minimizes the number of new users who must learn it.
Finally, we subtract the maximum frequency from the total number of problematic users to compute the minimum teachings required.
Go Solution
package main
func minimumTeachings(n int, languages [][]int, friendships [][]int) int {
languageSets := make([]map[int]bool, len(languages))
for i, langs := range languages {
languageSets[i] = make(map[int]bool)
for _, lang := range langs {
languageSets[i][lang] = true
}
}
needTeaching := make(map[int]bool)
for _, friendship := range friendships {
u := friendship[0] - 1
v := friendship[1] - 1
canCommunicate := false
for lang := range languageSets[u] {
if languageSets[v][lang] {
canCommunicate = true
break
}
}
if !canCommunicate {
needTeaching[u] = true
needTeaching[v] = true
}
}
languageCount := make(map[int]int)
for user := range needTeaching {
for lang := range languageSets[user] {
languageCount[lang]++
}
}
maxKnown := 0
for _, count := range languageCount {
if count > maxKnown {
maxKnown = count
}
}
return len(needTeaching) - maxKnown
}
The Go implementation mirrors the Python logic closely. Since Go does not have a built-in set type, maps with boolean values are used to simulate sets.
Language membership checks are performed with map[int]bool. The needTeaching structure is also implemented as a map to avoid duplicate users.
Unlike Python's isdisjoint(), Go manually checks whether two users share a language by iterating through one user's language map and checking membership in the other.
Integer overflow is not a concern because all values remain very small under the given constraints.
Worked Examples
Example 1
n = 2
languages = [[1], [2], [1,2]]
friendships = [[1,2], [1,3], [2,3]]
Step 1: Build language sets
| User | Languages |
|---|---|
| 1 | {1} |
| 2 | {2} |
| 3 | {1,2} |
Step 2: Process friendships
| Friendship | Shared Language? | Action |
|---|---|---|
| (1,2) | No | Add users 1 and 2 |
| (1,3) | Yes, language 1 | Ignore |
| (2,3) | Yes, language 2 | Ignore |
Now:
need_teaching = {1, 2}
Step 3: Count language frequencies
| User | Languages |
|---|---|
| 1 | {1} |
| 2 | {2} |
Frequency table:
| Language | Count |
|---|---|
| 1 | 1 |
| 2 | 1 |
Best language count:
max_known = 1
Step 4: Compute answer
answer = 2 - 1 = 1
Final answer:
1
Example 2
n = 3
languages = [[2], [1,3], [1,2], [3]]
friendships = [[1,4], [1,2], [3,4], [2,3]]
Step 1: Build language sets
| User | Languages |
|---|---|
| 1 | {2} |
| 2 | {1,3} |
| 3 | {1,2} |
| 4 | {3} |
Step 2: Process friendships
| Friendship | Shared Language? | Action |
|---|---|---|
| (1,4) | No | Add 1 and 4 |
| (1,2) | No | Add 1 and 2 |
| (3,4) | No | Add 3 and 4 |
| (2,3) | Yes, language 1 | Ignore |
Now:
need_teaching = {1,2,3,4}
Step 3: Count language frequencies
| User | Languages |
|---|---|
| 1 | {2} |
| 2 | {1,3} |
| 3 | {1,2} |
| 4 | {3} |
Frequency table:
| Language | Count |
|---|---|
| 1 | 2 |
| 2 | 2 |
| 3 | 2 |
Best language count:
max_known = 2
Step 4: Compute answer
answer = 4 - 2 = 2
Final answer:
2
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(f × k + m × k) | We process friendships and count languages for problematic users |
| Space | O(m + n) | Sets and frequency maps store users and language counts |
Here, f is the number of friendships, m is the number of users, and k is the average number of languages per user.
The friendship scan dominates the first phase, while counting language frequencies dominates the second phase. Since all constraints are capped at 500, the solution easily fits within limits.
Test Cases
from typing import List
class Solution:
def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
from collections import defaultdict
language_sets = [set(lang_list) for lang_list in languages]
need_teaching = set()
for u, v in friendships:
if language_sets[u - 1].isdisjoint(language_sets[v - 1]):
need_teaching.add(u - 1)
need_teaching.add(v - 1)
language_count = defaultdict(int)
for user in need_teaching:
for language in language_sets[user]:
language_count[language] += 1
return len(need_teaching) - max(language_count.values(), default=0)
solution = Solution()
assert solution.minimumTeachings(
2,
[[1], [2], [1, 2]],
[[1, 2], [1, 3], [2, 3]]
) == 1 # Provided example 1
assert solution.minimumTeachings(
3,
[[2], [1, 3], [1, 2], [3]],
[[1, 4], [1, 2], [3, 4], [2, 3]]
) == 2 # Provided example 2
assert solution.minimumTeachings(
3,
[[1], [1], [1]],
[[1, 2], [2, 3]]
) == 0 # Everyone already communicates
assert solution.minimumTeachings(
3,
[[1], [2], [3]],
[[1, 2], [2, 3]]
) == 1 # One language can resolve both friendships
assert solution.minimumTeachings(
4,
[[1, 2], [2, 3], [3, 4], [4]],
[[1, 2], [2, 3], [3, 4]]
) == 0 # All friendships already valid
assert solution.minimumTeachings(
2,
[[1], [2]],
[[1, 2]]
) == 1 # Single problematic friendship
assert solution.minimumTeachings(
5,
[[1], [2], [3], [4], [5]],
[[1, 2], [2, 3], [3, 4], [4, 5]]
) == 3 # Chain requiring optimal language choice
assert solution.minimumTeachings(
3,
[[1, 2], [2], [1]],
[[1, 2], [1, 3], [2, 3]]
) == 1 # Mixed shared and unshared friendships
Test Summary
| Test | Why |
|---|---|
| Example 1 | Validates basic functionality |
| Example 2 | Validates multiple problematic friendships |
| All users share a language | Ensures answer can be zero |
| Completely disconnected languages | Tests optimal language selection |
| Already valid network | Ensures unnecessary teaching is avoided |
| Single friendship | Smallest non-trivial case |
| Long chain of conflicts | Tests overlapping problematic users |
| Mixed valid and invalid friendships | Ensures only problematic pairs are considered |
Edge Cases
One important edge case occurs when every friendship pair already shares a common language. A careless implementation might still attempt to teach users unnecessarily. In this solution, such friendships are ignored entirely, leaving need_teaching empty. The final answer becomes 0 correctly.
Another subtle case occurs when the same user participates in multiple problematic friendships. A naive implementation could count the same user multiple times, inflating the answer. Using a set for need_teaching guarantees that each user is counted exactly once regardless of how many problematic friendships they appear in.
A third tricky case occurs when several candidate languages yield the same optimal answer. For example, multiple languages may already be known by the same number of problematic users. The implementation naturally handles this by taking the maximum frequency count. Since only the minimum number of teachings matters, ties do not affect correctness.
A final edge case involves users who already know many languages. Such users may already know the chosen teaching language even if they participate in problematic friendships. The frequency counting step correctly avoids teaching these users again because they contribute to the existing count for that language.