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 valuesThis 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.
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.
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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * f) given each language assessed with friendships.
Space Complexity: O(m*n) for arrays highlighting teachings required.
| 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. |
70 Leetcode problems in 5+ hours (every data structure) (full tutorial) • stoney codes • 750,521 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