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:

  1. Identify the users who cannot communicate with their friends due to language barriers.
  2. Among these users, count the occurrence of each known language.
  3. 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.

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:

1class Solution:
2    def minimumTeachings(
3        self, n: int, languages: List[List[int]], friendships: List[List[int]]
4    ) -> int:
5        # Helper function to check for common language between two users
6        def check(u, v):
7            for x in languages[u - 1]:
8                for y in languages[v - 1]:
9                    if x == y:
10                        return True
11            return False
12
13        # Set to track users who cannot communicate with at least one friend
14        s = set()
15        for u, v in friendships:
16            if not check(u, v):
17                s.add(u)
18                s.add(v)
19
20        # Counter to count the occurrences of each language among the users in set 's'
21        cnt = Counter()
22        for u in s:
23            for l in languages[u - 1]:
24                cnt[l] += 1
25
26        # Subtracting the maximum language occurrence from the number of users to teach
27        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.

Example 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 the languages 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}.
  • 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:

  1. Identify users who cannot communicate:

    • For friendship (1, 2), User 1 and User 2 share language 2, so they can communicate.
    • For friendship (3, 4), User 3 and User 4 do not share any common language, therefore they cannot communicate.
  2. 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}.

  3. Count the occurrences of each known language:

    • Users in set s know the following languages:
      • User 3 knows {3}.
      • User 4 knows {1}.
    • Counting these, we get that languages 1 and 3 are known by one user each in need of teaching.
  4. Determine the most common language among them:

    • Since both languages 1 and 3 are equally common (each known by one user who can't communicate), we can choose either to teach. Let's say we choose language 1 for maximum coverage.
  5. 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 equals 2 - 1 = 1.
    • We only need to teach 1 user (User 3) a new language to ensure all friends can communicate.

The Python solution identifies these steps programmatically and efficiently performs these calculations, arriving at the optimal solution with minimal teaching required.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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.

  1. The check function involves two nested loops over the languages spoken by users u and v. If m represents the maximum number of languages any user knows, this function could take up to O(m^2) time in the worst case.

  2. The outer loop for iterating over the friendships list, which calls the check function, runs k times where k is the number of friendships. So, this part of the algorithm will take O(k * m^2) time.

  3. In the worst case, the set s could include all users, which will, therefore, contain at most 2 * k elements, as each friendship involves two users.

  4. The counting of languages again requires an iteration over set s, and for each user in s, iterating over the maximum number of languages they know. In the worst case, this is O(k * m).

  5. The final step is finding the maximum value in the counter, which can take O(n) time, where n 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

  1. The check function operates in constant space.

  2. The set s can contain up to 2 * k elements, therefore O(k) space complexity.

  3. The cnt Counter objects can contain at most n key-value pairs representing the languages, thus O(n) space is needed.

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


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫