Number of People Aware of a Secret

Problem

Approach

Looks like a graph problem, but quickly realise that it would be an exponential solution as we will need to try every possibility for each broken pair. Took me a while to also realise that we only need to care about learning one language, and we just minimise the number of people we have to teach.

Complexity

• Time: $O(mn)$
• Space: $O(m+n)$

Code

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
        # create a set of broken pairs
        broken_pairs = set()
        for pA, pB in friendships:
            lA, lB = set(languages[pA-1]), set(languages[pB-1])
            if not lA & lB: 
                broken_pairs.add(pA)
                broken_pairs.add(pB)
        
        # create a hashtable of languages to people who know them
        lang_map = defaultdict(set)
        for i, langs in enumerate(languages):
            for lang in langs: lang_map[lang].add(i+1)
 
        # for every language, find the number of people that we need to teach
        # for the frienships to be complete
        res = float('inf')
        for lang in range(1, n+1):
            people_who_know_lang = lang_map[lang]
            res = min(res, len(broken_pairs) - len(people_who_know_lang & broken_pairs))
 
        return res