Minimum Number of People to Teach - Video Solutions

Problem Overview: You have n languages, a list of languages known by each user, and friendship pairs. Two friends must share at least one common language to communicate. You can teach a single language to any number of users. The goal is to choose a language and teach it to the minimum number of people so every friendship pair can communicate.

Approach 1: Simulate Teaching Each Language (Greedy Simulation) (Time: O(n * F * L), Space: O(U))

Try each language from 1..n as the teaching candidate. For every friendship pair, check if the two users already share a language. If they do not, mark both users as needing the candidate language. Use a set to avoid counting the same user multiple times. The minimum number of users across all candidate languages is the answer. This approach directly simulates the teaching process and works well when the number of languages is small.

Approach 2: Language Counting Approach (Time: O(F * L), Space: O(U))

First identify friendship pairs that cannot currently communicate. For each such pair, add both users to a set of problematic users. Only these users matter because everyone else already communicates with their friends. Count how many of these users already know each language using a hash map. The optimal language to teach is the one already known by the most users in this set. The number of people to teach becomes size(problematic_users) - max_language_count. This greedy counting trick removes the need to simulate every language separately.

Approach 3: Counting Maximum Communicable Language (Time: O(F * L), Space: O(n))

Convert each user's language list into a hash set for fast membership checks. Iterate through each friendship pair and detect pairs without a shared language using set lookups. Collect all users from such pairs. Then count how many of these users know each language. The language with the highest frequency maximizes existing communication and minimizes teaching. This is the most common editorial approach and relies heavily on hash table counting combined with a greedy decision.

Approach 4: Bipartite Graph Optimization (Time: O(F * L), Space: O(U + n))

Model users and languages as a bipartite graph where edges represent "user knows language". First filter friendship edges where users cannot communicate. Only users involved in those edges remain relevant. Count connections from these users to languages and choose the language with the highest coverage. Graph thinking helps reason about coverage and constraints, though the final implementation reduces to counting frequencies.

Recommended for interviews: The language counting approach is typically expected. Start by detecting friendships that cannot communicate, then count which language already appears most among those users. This shows understanding of array traversal, hash-based counting, and greedy optimization. Mentioning the simulation approach first demonstrates problem exploration, but the counting solution demonstrates stronger algorithmic insight.