Problem Statement in English

In a social network, each person can speak multiple languages. However, not everyone speaks the same languages.

Some friendships exist between people who do not share a common language, leading to communication problems.

The goal is to minimize the number of people who need to be taught a new language so that all friendships can be maintained.

languages[i] is a list of languages that the i-th person can speak, and friendships[j] = [u_j, v_j] indicates that person u_j is friends with person v_j. A friendship can be maintained if both people in the friendship can speak at least one common language.

Approach

We need to identify friendships where the two people do not share any common language.

Then, we can determine the most commonly spoken language among those problematic friendships.

Our answer is the total number of people involved in these problematic friendships minus the number of people who already speak the most common language.

Solution in Python


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

        c = defaultdict(int)
        problems = set()

        for u, v in friendships:
            if not languages[u - 1] & languages[v - 1]:
                problems.add(u - 1)
                problems.add(v - 1)

        for u in problems:
            for l in languages[u]:
                c[l] += 1

        return len(problems) - max(c.values(), default=0)

Complexity

  • Time: $O(n + m)$, where $n$ is the number of people and $m$ is the number of friendships.

  • Space: $O(n)$ for the language sets and the counter.

Mistakes I Made

I messed up the reconciliation step after identifying the problematic friendships.

And we are done.