Minimum Number of People to Teach LeetCode solution in Python

1
# Runtime: 2444 ms (Top 20.45%) | Memory: 28.6 MB (Top 5.68%)
2
class Solution:
3
    def minimumTeachings(
4
        self, n: int, languages: List[List[int]], friendships: List[List[int]]
5
    ) -> int:
6
        """
7
        1. Find out users who need to be taught
8
        2. If no user needs to be taught, return 0
9
        3. For all users who need to be taught a language, find the most popular language among them
10
        4. Teach that language to rest of the users who need to be taught.
11
        """
12
        need_to_be_taught = set()
13
        languages = [set(language) for language in languages]
14

15
        # 1. Find out users who needs to be taught
16
        for user1, user2 in friendships:
17
            # Adjust the 1 based indexing to 0 based indexing
18
            user1 = user1 - 1
19
            user2 = user2 - 1
20
            if not (languages[user1] & languages[user2]):
21
                need_to_be_taught.update([user1, user2])
22

23
        # 2. If no user needs to be taught, return 0
24
        if not need_to_be_taught:
25
            return 0
26

27
        # 3. For all users who needs to be taught a language, find the most popular language among them
28
        language_spoken_by = collections.defaultdict(int)
29
        for user in need_to_be_taught:
30
            # for each user increment the count of languages he can speak
31
            for language in languages[user]:
32
                language_spoken_by[language] += 1
33

34
        # find occurrence of language spoken by maximum users who can't communicate with each other
35
        popular_language_count = max(language_spoken_by.values())
36

37
        # 4. Teach that language to rest of the users who need to be taught.
38
        return len(need_to_be_taught) - popular_language_count