Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Only friendships with no shared language need intervention. For those friendships, teaching one selected language works if every involved user knows it afterward. The best language is therefore the one already known by the largest number of affected users.

Approach

Convert each user's languages to a set. Check every friendship and collect both endpoints only when their language sets have empty intersection, converting the one-based user identifiers to indices. Count language frequencies across this set of affected users, counting each user once. Subtract the largest frequency from the number of affected users. If no friendship needs help, both terms are zero and the answer is zero.

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
        languages = [set(l) for l in languages]
        cannot_communicate = set()

        for a, b in friendships:
            a -= 1
            b -= 1
            # if any(x == y for x in languages[a] for y in languages[b]): continue
            if languages[a] & languages[b]:
                continue
            # & is intersection of sets
            cannot_communicate.add(a)
            cannot_communicate.add(b)

        fm = defaultdict(int)

        for friend in cannot_communicate:
            for l in languages[friend]:
                fm[l] += 1

        return len(cannot_communicate) - max(fm.values() or [0])

Complexity analysis

Let f be the number of friendships, L the total user-language memberships, and d the maximum languages known by one user. Time: O(f * d + L). Auxiliary space: O(L) for language sets, affected users, and frequency counts.