1733. Minimum Number of People to Teach
Problem Description
In a given social network, there are m
users and certain friendships between them. A friendship allows two users to communicate only if there's a common language between them. There are n
distinct languages, and each user may know one or more languages. The languages
array consists of sets, each set containing the languages known by the i-th
user. The friendships
array consists of pairs, with each pair representing a friendship between two users.
The task is to determine the minimum number of users needed to teach exactly one language so that every friendship in the network has a common language. This will enable all friends to communicate with each other. It's important to note that friendships are not transitive, meaning that mutual friendships do not imply indirect friendships.
Intuition
To solve this problem, we start by identifying all pairs of users within the friendships
array that cannot communicate because they do not share a common language. We will store these users in a set to avoid duplication, as teaching a user multiple times is redundant.
After determining the set of users who need to be taught a new language, we will count how many of these users know each language. This is done because the optimal solution would likely involve teaching the most common language among these users, as it will reduce the total number of teachings required.
The key steps in the intuition behind the solution are:
- Identify the users who cannot communicate with their friends due to language barriers.
- Among these users, count the occurrence of each known language.
- Deduct the highest occurrence from the total users who need to be taught to obtain the minimum number of teachings.
The provided Python solution precisely follows this approach, using a helper function check
to test if two users can communicate and accumulates the users who need to be taught in a set. It then uses a Counter
to tally the languages, and subtracts the most common language's count from the total number of users to teach.
Learn more about Greedy patterns.
Solution Approach
The solution follows a straightforward approach which can be broken down into several steps with corresponding algorithms and data structures.
Firstly, we define a check
function that takes two user IDs as inputs and checks whether those two users share at least one language. This function iterates over the language sets of both users (user u
and user v
), checking for a common language. If a common language is found, it returns True
, and if not, False
.
Secondly, we create a set s
to store all users who cannot communicate with their friends. We iterate through the friendships
list and use the check
function to determine if a user pair does not have a common language. If not, both users are added to the set s
, as they will require teaching a common language to communicate.
Next, after identifying all users who require teaching, we use a Counter
from Python's collections
module to keep track of the occurrences of each language among these users. The Counter
is a dictionary subclass designed for counting hashable objects. Here, it is particularly useful because it allows us to easily increment counts of each language known by the users in set s
.
Finally, we identify the language known by the largest number of users who need language teaching by using the max
function on the values of the Counter
object. We subtract this value from the length of set s
, which gives us the minimum number of users who need to be taught a new language. By teaching the most common language among those who can't communicate, we minimize the number of teachings needed.
The solution leverages Python's set and dictionary (via Counter
) data structures to efficiently keep track of unique elements and their counts respectively. The use of these data structures, along with effective use of iteration and condition checking, allows for a solution that is relatively easy to understand and efficient in terms of both time and space complexity.
Here's how the implementation looks in reference to the steps above:
class Solution:
def minimumTeachings(
self, n: int, languages: List[List[int]], friendships: List[List[int]]
) -> int:
# Helper function to check for common language between two users
def check(u, v):
for x in languages[u - 1]:
for y in languages[v - 1]:
if x == y:
return True
return False
# Set to track users who cannot communicate with at least one friend
s = set()
for u, v in friendships:
if not check(u, v):
s.add(u)
s.add(v)
# Counter to count the occurrences of each language among the users in set 's'
cnt = Counter()
for u in s:
for l in languages[u - 1]:
cnt[l] += 1
# Subtracting the maximum language occurrence from the number of users to teach
return len(s) - max(cnt.values(), default=0)
The solution's time complexity is O(F*L^2) where F is the number of friendships and L is the maximum number of languages a user can know. The space complexity is O(U + L) where U is the number of users who can't communicate with their friends.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Suppose we have the following scenario:
- There are
n = 3
languages. - There are
m = 4
users with their known languages in thelanguages
array:- User 1 knows languages
{1, 2}
. - User 2 knows languages
{2, 3}
. - User 3 knows only language
{3}
. - User 4 knows only language
{1}
.
- User 1 knows languages
- The
friendships
array indicates friendship pairs:(1, 2)
: User 1 is friends with User 2.(3, 4)
: User 3 is friends with User 4.
- We want to enable all friends to communicate with each other by teaching the least number of users a new language.
Now, we apply the solution steps:
-
Identify users who cannot communicate:
- For friendship
(1, 2)
, User 1 and User 2 share language2
, so they can communicate. - For friendship
(3, 4)
, User 3 and User 4 do not share any common language, therefore they cannot communicate.
- For friendship
-
Users who need to learn a new language: User 3 and User 4 should be considered for learning a new language. We add them to the set
s = {3, 4}
. -
Count the occurrences of each known language:
- Users in set
s
know the following languages:- User 3 knows
{3}
. - User 4 knows
{1}
.
- User 3 knows
- Counting these, we get that languages
1
and3
are known by one user each in need of teaching.
- Users in set
-
Determine the most common language among them:
- Since both languages
1
and3
are equally common (each known by one user who can't communicate), we can choose either to teach. Let's say we choose language1
for maximum coverage.
- Since both languages
-
Calculate the minimum number of users to teach:
- Since we are teaching the most common language (language
1
in our case), and one user (User 4) already knows it, we need to teach only one additional user (User 3). - Thus, the result is
len(s) - max(cnt.values())
which equals2 - 1 = 1
. - We only need to teach
1
user (User 3) a new language to ensure all friends can communicate.
- Since we are teaching the most common language (language
The Python solution identifies these steps programmatically and efficiently performs these calculations, arriving at the optimal solution with minimal teaching required.
Solution Implementation
1from typing import List
2from collections import Counter
3
4class Solution:
5 def minimumTeachings(self, total_languages: int, user_languages: List[List[int]], friendships: List[List[int]]) -> int:
6 # Define a function to check if there is a common language between two users
7 def has_common_language(user1, user2):
8 for language1 in user_languages[user1 - 1]:
9 for language2 in user_languages[user2 - 1]:
10 if language1 == language2:
11 return True
12 return False
13
14 # Initialize a set to keep track of users who need a common language
15 users_needing_language = set()
16 # Iterate over the friendships to find pairs of users without a common language
17 for user1, user2 in friendships:
18 if not has_common_language(user1, user2):
19 users_needing_language.add(user1)
20 users_needing_language.add(user2)
21
22 # Create a counter to count the occurrences of each language among users needing it
23 language_count = Counter()
24 for user in users_needing_language:
25 for language in user_languages[user - 1]:
26 language_count[language] += 1
27
28 # The minimum number of teachings is the number of users needing a language
29 # minus the highest occurrence count of any single language
30 # Use default=0 in case count.values() is empty to avoid ValueErrors
31 max_common_language = max(language_count.values(), default=0)
32 return len(users_needing_language) - max_common_language
33
1class Solution {
2
3 // Method to compute the minimum number of teachings required
4 public int minimumTeachings(int totalLanguages, int[][] userLanguages, int[][] friendships) {
5 // Set to maintain unique users that need a language teaching
6 Set<Integer> usersToTeach = new HashSet<>();
7
8 // Check for each pair of friendships whether they have a common language
9 for (int[] friendship : friendships) {
10 int user1 = friendship[0];
11 int user2 = friendship[1];
12 // If two users do not share a common language, add them to the set
13 if (!shareCommonLanguage(user1, user2, userLanguages)) {
14 usersToTeach.add(user1);
15 usersToTeach.add(user2);
16 }
17 }
18
19 // If no teaching is required, return 0
20 if (usersToTeach.isEmpty()) {
21 return 0;
22 }
23
24 // Array to count how many users know each language
25 int[] languageCount = new int[totalLanguages + 1];
26
27 // For all users that need teaching, count the languages they know
28 for (int user : usersToTeach) {
29 for (int language : userLanguages[user - 1]) {
30 languageCount[language]++;
31 }
32 }
33
34 // Find the language known by the maximum number of users
35 int maxLanguageCount = 0;
36 for (int count : languageCount) {
37 maxLanguageCount = Math.max(maxLanguageCount, count);
38 }
39
40 // The minimum number of teachings is the number of users to teach
41 // minus the maximum common language count
42 return usersToTeach.size() - maxLanguageCount;
43 }
44
45 // Helper method to check if two users share a common language
46 private boolean shareCommonLanguage(int user1, int user2, int[][] userLanguages) {
47 for (int language1 : userLanguages[user1 - 1]) {
48 for (int language2 : userLanguages[user2 - 1]) {
49 if (language1 == language2) {
50 return true;
51 }
52 }
53 }
54 return false;
55 }
56}
57
1#include <vector>
2#include <unordered_set>
3#include <algorithm>
4
5class Solution {
6public:
7 // Calculates the minimum number of languages needed to be taught
8 // such that every friendship is possible without a language barrier.
9 int minimumTeachings(int totalLanguages, std::vector<std::vector<int>>& languages, std::vector<std::vector<int>>& friendships) {
10 std::unordered_set<int> usersNeedingTeaching; // Contains IDs of users who need teaching
11
12 // Check if users in each friendship speak a common language
13 for (auto& friendship : friendships) {
14 int user1 = friendship[0], user2 = friendship[1];
15 // If users don't have a common language, add them to the set
16 if (!shareCommonLanguage(user1, user2, languages)) {
17 usersNeedingTeaching.insert(user1);
18 usersNeedingTeaching.insert(user2);
19 }
20 }
21
22 // If no users need teaching, return 0
23 if (usersNeedingTeaching.empty()) {
24 return 0;
25 }
26
27 // Count how many users speak each language
28 std::vector<int> languageCounts(totalLanguages + 1);
29 for (int user : usersNeedingTeaching) {
30 for (int& language : languages[user - 1]) {
31 ++languageCounts[language];
32 }
33 }
34
35 // The number of teachings required is the size of users needing teaching
36 // minus the most common language among them
37 return usersNeedingTeaching.size() - *std::max_element(languageCounts.begin(), languageCounts.end());
38 }
39
40private:
41 // Returns true if the two users share at least one common language
42 bool shareCommonLanguage(int user1, int user2, std::vector<std::vector<int>>& languages) {
43 for (int language1 : languages[user1 - 1]) {
44 for (int language2 : languages[user2 - 1]) {
45 if (language1 == language2) {
46 return true; // A common language is found
47 }
48 }
49 }
50 return false; // No common language between the two users
51 }
52};
53
1type Languages = number[][];
2type Friendships = number[][];
3
4// Check if two users share a common language
5function shareCommonLanguage(user1: number, user2: number, languages: Languages): boolean {
6 const langUser1 = languages[user1 - 1];
7 const langUser2 = languages[user2 - 1];
8
9 for (const language1 of langUser1) {
10 for (const language2 of langUser2) {
11 if (language1 === language2) {
12 // A common language has been found
13 return true;
14 }
15 }
16 }
17 // No common language exists between user1 and user2
18 return false;
19}
20
21// Calculate the minimum number of languages needed to be taught such that every friendship is possible without a language barrier
22function minimumTeachings(totalLanguages: number, languages: Languages, friendships: Friendships): number {
23 // Holds the IDs of users who need language teaching
24 const usersNeedingTeaching = new Set<number>();
25
26 // Iterate through each friendship
27 for (const friendship of friendships) {
28 const [user1, user2] = friendship;
29
30 // If users do not have a common language, add them to the set of users needing teaching
31 if (!shareCommonLanguage(user1, user2, languages)) {
32 usersNeedingTeaching.add(user1);
33 usersNeedingTeaching.add(user2);
34 }
35 }
36
37 // If no users need teaching, return 0
38 if (usersNeedingTeaching.size === 0) {
39 return 0;
40 }
41
42 // Initialize a count of how many users speak each language
43 const languageCounts: number[] = new Array(totalLanguages + 1).fill(0);
44
45 // Count the number of users that speak each language
46 for (const user of usersNeedingTeaching) {
47 const spokenLanguages = languages[user - 1];
48 for (const language of spokenLanguages) {
49 languageCounts[language]++;
50 }
51 }
52
53 // Find the most common language among users who need teaching
54 const maxLanguageCount = Math.max(...languageCounts);
55
56 // Calculate the minimum number of teachings required, which is equal to
57 // the total number of users in need of teaching minus the count of the most common language
58 return usersNeedingTeaching.size - maxLanguageCount;
59}
60
61// Example usage:
62const totalLanguages = 3;
63const languages: Languages = [[1], [2], [3], [3]];
64const friendships: Friendships = [[1, 4], [1, 2], [3, 4], [2, 3]];
65const results = minimumTeachings(totalLanguages, languages, friendships);
66console.log(results); // Output: the minimum number of languages to teach
67
Time and Space Complexity
Time Complexity
The provided code consists of two major parts - the check for whether each pair of friends speak a common language and the counting of languages among the users who need to be taught.
-
The
check
function involves two nested loops over the languages spoken by usersu
andv
. Ifm
represents the maximum number of languages any user knows, this function could take up toO(m^2)
time in the worst case. -
The outer loop for iterating over the
friendships
list, which calls thecheck
function, runsk
times wherek
is the number of friendships. So, this part of the algorithm will takeO(k * m^2)
time. -
In the worst case, the set
s
could include all users, which will, therefore, contain at most2 * k
elements, as each friendship involves two users. -
The counting of languages again requires an iteration over set
s
, and for each user ins
, iterating over the maximum number of languages they know. In the worst case, this isO(k * m)
. -
The final step is finding the maximum value in the counter, which can take
O(n)
time, wheren
is the total number of languages.
Combining these elements, the worst-case time complexity of the code is the sum of these complexities: O(k * m^2 + k * m + n)
.
Space Complexity
-
The
check
function operates in constant space. -
The set
s
can contain up to2 * k
elements, thereforeO(k)
space complexity. -
The
cnt
Counter objects can contain at mostn
key-value pairs representing the languages, thusO(n)
space is needed. -
Temporary space for iterating and counting - This space is constant.
The combined space complexity of the provided code is the maximum of these, which is O(k + n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!