Skip to main content
Talentd

Minimum Number of People to Teach - Solution & Explanation

MediumArrayHash TableGreedy24 min readAsked at: Amazon, Google, Bloomberg +1
Practice this problem

Problem Statement

On a social network consisting of m users and some friendships between users, two users can communicate with each other if they know a common language.

You are given an integer n, an array languages, and an array friendships where:

  • There are n languages numbered 1 through n,
  • languages[i] is the set of languages the i​​​​​​th​​​​ user knows, and
  • friendships[i] = [u​​​​​​i​​​, v​​​​​​i] denotes a friendship between the users u​​​​​​​​​​​i​​​​​ and vi.

You can choose one language and teach it to some users so that all friends can communicate with each other. Return the minimum number of users you need to teach.

Note that friendships are not transitive, meaning if x is a friend of y and y is a friend of z, this doesn't guarantee that x is a friend of z.

 

Example 1:

Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
Output: 1
Explanation: You can either teach user 1 the second language or user 2 the first language.

Example 2:

Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
Output: 2
Explanation: Teach the third language to users 1 and 3, yielding two users to teach.

 

Constraints:

  • 2 <= n <= 500
  • languages.length == m
  • 1 <= m <= 500
  • 1 <= languages[i].length <= n
  • 1 <= languages[i][j] <= n
  • 1 <= u​​​​​​i < v​​​​​​i <= languages.length
  • 1 <= friendships.length <= 500
  • All tuples (u​​​​​i, v​​​​​​i) are unique
  • languages[i] contains only unique values

Approach Overview

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.

Approach 1: Language Counting Approach

This approach focuses on analyzing each language to determine which one minimizes the number of new teachings. For each language, calculate how many users need to learn it to make all friendships communicable. Choose the language with the least number of teachings.

The function minimumTeachings iterates over each friendship to identify pairs that cannot communicate. For each language, it checks how many users need to learn that language to resolve all communication gaps. The language with the least number of necessary teachings is chosen.

Code

Python

Python

Complexity

Time Complexity: O(m * n), where m is the number of friendships and n is the number of languages.
Space Complexity: O(m) for storing the pairs that cannot communicate.

Try this approach in the editor →

Approach 2: Simulate Teaching Approach

This approach involves simulating teaching different languages to users who cannot currently communicate with their friends. By iterating through each language, determine the set of users that need to learn the language to resolve all uncommunicable friendships, then choose the minimal set.

The approach starts by identifying friend pairs that cannot communicate. For each language, determine how many distinct users must learn it to ensure all uncommunicable friendships are resolved. The result is the minimal teaching effort required.

Code

Python

Python

Complexity

Time Complexity: O(m * n), where m is the number of friendships and n is the number of languages.
Space Complexity: O(m + n) for tracking uncommunicable friendships and user counts per language.

Try this approach in the editor →

Approach 3: Approach 1: Counting Maximum Communicable Language

Idea: Identify a language that, once learned by specific users, transforms unmatched friends into communicable pairs. For each language, calculate how many people need to learn it to cover all problematic friendships.

Steps:

  • Identify all friendship pairs that cannot communicate.
  • For each language, determine number of users who need to be taught this language to allow every friendship pair that's currently unable to communicate to do so.
  • Select the language causing the least disruptions (i.e., minimal number of teachings).

This solution uses a 2D array to track language proficiency: languages[i][j] tells if user 'i' knows language 'j'. It checks each friendship pair if there’s already a common language, and populates communicability status. For each language, it calculates how many people need to learn it to convert non-communicable friendships to communicable. The minimum such count is the answer.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(f * n * m) - Checking and counting through each language and friendship.
Space Complexity: O(m*n) - 2D arrays for language and communication tracking.

Try this approach in the editor →

Approach 4: Approach 2: Bipartite Graph Optimization

Idea: Conceptually represent the problem as a bipartite graph. Users are vertices, and languages are connecting edges. By teaching a language, we ensure that each edge becomes valid. We focus on the minimum vertex cover, which translates to minimum teachings.

Steps:

  • Formulate a graph where a missing edge signifies the need for teaching.
  • Use an algorithm to ascertain the minimum vertex cover, representing users requiring language instruction.
  • Emphasis on reducing coverage/minimizing teachings.

This C solution creates a grid marking language proficiency, noting users needing teaching due to communication fails. It replaces counting through states and uses bipartite graph principles to find minimum unavoidable lessons.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * f) given each language assessed with friendships.
Space Complexity: O(m*n) for arrays highlighting teachings required.

Try this approach in the editor →

Approach 5: Simulation + Statistics

For each friendship, if the sets of languages known by the two people do not intersect, we need to teach one language so that they can communicate. We add these people to a hash set s.

Then, for each language, we count how many people in set s know that language and find the maximum count, denoted as mx. The answer is |s| - mx, where |s| is the size of set s.

The time complexity is O(m^2 times k). Here, m is the number of languages, and k is the number of friendships.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Language Counting Approach

Time Complexity: O(m * n), where m is the number of friendships and n is the number of languages.
Space Complexity: O(m) for storing the pairs that cannot communicate.

Simulate Teaching Approach

Time Complexity: O(m * n), where m is the number of friendships and n is the number of languages.
Space Complexity: O(m + n) for tracking uncommunicable friendships and user counts per language.

Approach 1: Counting Maximum Communicable Language

Time Complexity: O(f * n * m) - Checking and counting through each language and friendship.
Space Complexity: O(m*n) - 2D arrays for language and communication tracking.

Approach 2: Bipartite Graph Optimization

Time Complexity: O(n * f) given each language assessed with friendships.
Space Complexity: O(m*n) for arrays highlighting teachings required.

Simulation + Statistics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulate Teaching Each LanguageO(n * F * L)O(U)Good for understanding the brute-force idea and when language count is small
Language Counting ApproachO(F * L)O(U)Best general solution; avoids unnecessary simulation
Counting Maximum Communicable LanguageO(F * L)O(n)Interview-friendly optimal approach using hash counting
Bipartite Graph OptimizationO(F * L)O(U + n)Useful for reasoning about user-language relationships as a graph

Video Solution

Minimum Number of People to Teach | Logical Reasoning | Leetcode 1733 | codestorywithMIK • codestorywithMIK • 13,173 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Number of People to Teach easy or hard?
The problem is rated Medium because the brute-force idea is straightforward but identifying the greedy counting optimization requires insight. Once you focus only on users in non-communicating friendships and maximize the already-known language, the implementation becomes relatively simple.
How to solve Minimum Number of People to Teach in O(n)?
Strict O(n) is not typical because each friendship pair must be checked for shared languages. The closest optimal solution runs in O(F * L). It filters friendships without a common language, collects affected users, counts language frequencies among them, and selects the language that minimizes additional teaching.
Minimum Number of People to Teach Python or Java solution?
Implementations typically convert each user's languages into a set, scan friendships to find pairs without shared languages, collect affected users, and count language frequencies. The same logic works in Python, Java, C++, C#, and JavaScript using sets and hash maps.
What is the best approach for Minimum Number of People to Teach?
The most efficient approach is the language counting (greedy) method. First identify friendship pairs that cannot communicate and collect all users involved. Count how many of those users already know each language, then choose the language with the maximum count. The number of people to teach equals total problematic users minus that maximum.
Is Minimum Number of People to Teach asked at Google/Amazon/Meta?
Greedy counting and communication optimization problems similar to this appear in interviews at companies like Amazon, Google, and Meta. The problem tests hash set usage, greedy decision making, and efficient pair validation, which are common interview patterns.
What data structure is used in Minimum Number of People to Teach?
The solution primarily uses hash sets and hash maps. Sets allow fast checks to see whether two users share a language, and hash maps count how many users know each language among the problematic group. Arrays are also used to store each user's language list.
What is the time complexity of Minimum Number of People to Teach?
The optimal solution runs in O(F * L) time, where F is the number of friendship pairs and L is the average number of languages known per user. Each friendship pair is checked for a common language, and then language frequencies are counted among the affected users. Space complexity is typically O(U) for storing the set of users involved in communication failures.

Ready to solve this problem?

Practice Minimum Number of People to Teach with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays