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:
n languages numbered 1 through n,languages[i] is the set of languages the ith user knows, andfriendships[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 ifx 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 <= 500languages.length == m1 <= m <= 5001 <= languages[i].length <= n1 <= languages[i][j] <= n1 <= ui < vi <= languages.length1 <= friendships.length <= 500(ui, vi) are uniquelanguages[i] contains only unique valuesProblem Overview: You have n languages, a list of languages known by each user, and friendship pairs. Two friends must share at least one common language to communicate. You can teach a single language to any number of users. The goal is to choose a language and teach it to the minimum number of people so every friendship pair can communicate.
Approach 1: Simulate Teaching Each Language (Greedy Simulation) (Time: O(n * F * L), Space: O(U))
Try each language from 1..n as the teaching candidate. For every friendship pair, check if the two users already share a language. If they do not, mark both users as needing the candidate language. Use a set to avoid counting the same user multiple times. The minimum number of users across all candidate languages is the answer. This approach directly simulates the teaching process and works well when the number of languages is small.
Approach 2: Language Counting Approach (Time: O(F * L), Space: O(U))
First identify friendship pairs that cannot currently communicate. For each such pair, add both users to a set of problematic users. Only these users matter because everyone else already communicates with their friends. Count how many of these users already know each language using a hash map. The optimal language to teach is the one already known by the most users in this set. The number of people to teach becomes size(problematic_users) - max_language_count. This greedy counting trick removes the need to simulate every language separately.
Approach 3: Counting Maximum Communicable Language (Time: O(F * L), Space: O(n))
Convert each user's language list into a hash set for fast membership checks. Iterate through each friendship pair and detect pairs without a shared language using set lookups. Collect all users from such pairs. Then count how many of these users know each language. The language with the highest frequency maximizes existing communication and minimizes teaching. This is the most common editorial approach and relies heavily on hash table counting combined with a greedy decision.
Approach 4: Bipartite Graph Optimization (Time: O(F * L), Space: O(U + n))
Model users and languages as a bipartite graph where edges represent "user knows language". First filter friendship edges where users cannot communicate. Only users involved in those edges remain relevant. Count connections from these users to languages and choose the language with the highest coverage. Graph thinking helps reason about coverage and constraints, though the final implementation reduces to counting frequencies.
Recommended for interviews: The language counting approach is typically expected. Start by detecting friendships that cannot communicate, then count which language already appears most among those users. This shows understanding of array traversal, hash-based counting, and greedy optimization. Mentioning the simulation approach first demonstrates problem exploration, but the counting solution demonstrates stronger algorithmic insight.
This approach focuses on analyzing each language to determine which one minimizes the number of new teachings. For each language, calculate how many users need to learn it to make all friendships communicable. Choose the language with the least number of teachings.
The function minimumTeachings iterates over each friendship to identify pairs that cannot communicate. For each language, it checks how many users need to learn that language to resolve all communication gaps. The language with the least number of necessary teachings is chosen.
Python
Time Complexity: O(m * n), where m is the number of friendships and n is the number of languages.
Space Complexity: O(m) for storing the pairs that cannot communicate.
This approach involves simulating teaching different languages to users who cannot currently communicate with their friends. By iterating through each language, determine the set of users that need to learn the language to resolve all uncommunicable friendships, then choose the minimal set.
The approach starts by identifying friend pairs that cannot communicate. For each language, determine how many distinct users must learn it to ensure all uncommunicable friendships are resolved. The result is the minimal teaching effort required.
Python
Time Complexity: O(m * n), where m is the number of friendships and n is the number of languages.
Space Complexity: O(m + n) for tracking uncommunicable friendships and user counts per language.
Idea: Identify a language that, once learned by specific users, transforms unmatched friends into communicable pairs. For each language, calculate how many people need to learn it to cover all problematic friendships.
Steps:
This solution uses a 2D array to track language proficiency: languages[i][j] tells if user 'i' knows language 'j'. It checks each friendship pair if there’s already a common language, and populates communicability status. For each language, it calculates how many people need to learn it to convert non-communicable friendships to communicable. The minimum such count is the answer.
Time Complexity: O(f * n * m) - Checking and counting through each language and friendship.
Space Complexity: O(m*n) - 2D arrays for language and communication tracking.
Idea: Conceptually represent the problem as a bipartite graph. Users are vertices, and languages are connecting edges. By teaching a language, we ensure that each edge becomes valid. We focus on the minimum vertex cover, which translates to minimum teachings.
Steps:
This C solution creates a grid marking language proficiency, noting users needing teaching due to communication fails. It replaces counting through states and uses bipartite graph principles to find minimum unavoidable lessons.
Time Complexity: O(n * f) given each language assessed with friendships.
Space Complexity: O(m*n) for arrays highlighting teachings required.
For each friendship, if the sets of languages known by the two people do not intersect, we need to teach one language so that they can communicate. We add these people to a hash set s.
Then, for each language, we count how many people in set s know that language and find the maximum count, denoted as mx. The answer is |s| - mx, where |s| is the size of set s.
The time complexity is O(m^2 times k). Here, m is the number of languages, and k is the number of friendships.
| Approach | Complexity |
|---|---|
| Language Counting Approach | Time Complexity: O(m * n), where m is the number of friendships and n is the number of languages. |
| Simulate Teaching Approach | Time Complexity: O(m * n), where m is the number of friendships and n is the number of languages. |
| Approach 1: Counting Maximum Communicable Language | Time Complexity: O(f * n * m) - Checking and counting through each language and friendship. |
| Approach 2: Bipartite Graph Optimization | Time Complexity: O(n * f) given each language assessed with friendships. |
| Simulation + Statistics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Teaching Each Language | O(n * F * L) | O(U) | Good for understanding the brute-force idea and when language count is small |
| Language Counting Approach | O(F * L) | O(U) | Best general solution; avoids unnecessary simulation |
| Counting Maximum Communicable Language | O(F * L) | O(n) | Interview-friendly optimal approach using hash counting |
| Bipartite Graph Optimization | O(F * L) | O(U + n) | Useful for reasoning about user-language relationships as a graph |
Minimum Number of People to Teach | Logical Reasoning | Leetcode 1733 | codestorywithMIK • codestorywithMIK • 12,858 views views
Watch 9 more video solutions →Practice Minimum Number of People to Teach with our built-in code editor and test cases.
Practice on FleetCode