Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Minimum Number of People to Teach solution and explanation

MediumArrayGreedyHash Table9 min read67.7% acceptanceUpdated 9 Apr 2026
Asked atDuolingoGoogleAmazonBloomberg
Practise Minimum Number of People to Teach
27:27
Minimum Number of People to Teach | Logical Reasoning | Leetcode 1733 | codestorywithMIKcodestorywithMIK · 27:27 · 13K viewsWatch on YouTube
9 more videos on this problem
  1. Minimum Number of People to Teach | Logical Reasoning | Leetcode 1733 | codestorywithMIKcodestorywithMIK · 27:27 · 13K views
  2. LeetCode 1733. Minimum Number of People to Teach - Interview Prep Ep 116Fisher Coder · 17:30 · 1K views
  3. Minimum Number of People to Teach | LeetCode 1733 | Simple Solution with IntuitionSanyam IIT Guwahati · 16:48 · 1K views
  4. 1733. Minimum Number of People to Teach | Leetcode Daily - PythonLeetcode Daily · 6:55 · 1K views
  5. Minimum Number of People to Teach | Leetcode 1733Techdose · 27:39 · 859 views
  6. 1733. Minimum Number of People to Teach (Leetcode Medium)Programming Live with Larry · 16:57 · 578 views
  7. Daily Leetcode #1989: Sep 10, 2025 - 1733. Minimum Number of People to TeachProgramming Live with Larry · 18:24 · 565 views
  8. 1733. Minimum Number of People to Teach | Intuitive Greedy Solution | Leetcode Daily ChallengeEye on AI and DSA · 21:34 · 392 views
  9. Leetcode 1733. Minimum Number of People to Teach | Greedy + Set Intersection | Python SolutionStatLearn Tech · 17:15 · 340 views
  10. Minimum Number of People to Teach | LeetCode 1733 - Pythonimpoldev · 12:35 · 302 views

The problem

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.

def minimumTeachings(n, languages, friendships):
    def can_communicate(user1, user2):
        return len(set(languages[user1 - 1]).intersection(languages[user2 - 1])) > 0

    users_to_teach = [0] * n
    cannot_communicate = []

    for u, v in friendships:
        if not can_communicate(u, v):
            cannot_communicate.append((u, v))

    if not cannot_communicate:
        return 0

    for i in range(1, n + 1):
        users_needing_teaching = set()
        for u, v in cannot_communicate:
            if i not in languages[u - 1]:
                users_needing_teaching.add(u)
            if i not in languages[v - 1]:
                users_needing_teaching.add(v)

        users_to_teach[i - 1] = len(users_needing_teaching)

    return min(users_to_teach)

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.

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.

def minimumTeachings(n, languages, friendships):
    from collections import defaultdict

    def find_people_who_cant_communicate(languages, friendships):
        cant_communicate = []
        for u, v in friendships:
            if set(languages[u - 1]).intersection(languages[v - 1]) == set():
                cant_communicate.append((u, v))
        return cant_communicate

    cant_communicate = find_people_who_cant_communicate(languages, friendships)
    if not cant_communicate:
        return 0

    language_count = defaultdict(int)

    for lang in range(1, n + 1):
        users_to_teach = set()
        for u, v in cant_communicate:
            if lang not in languages[u - 1]:
                users_to_teach.add(u)
            if lang not in languages[v - 1]:
                users_to_teach.add(v)
        language_count[lang] = len(users_to_teach)

    return min(language_count.values())

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.

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).
def minimumTeachings(n, languages, friendships):
    from collections import defaultdict

    lang_known = [set(l) for l in languages]

    min_teach = float('inf')

    for lang in range(1, n + 1):
        to_teach = set()

        for u, v in friendships:
            u -= 1
            v -= 1

            if lang not in lang_known[u] and lang not in lang_known[v]:
                if lang not in lang_known[u]: to_teach.add(u)
                if lang not in lang_known[v]: to_teach.add(v)

        min_teach = min(min_teach, len(to_teach))

    return min_teach
import java.util.*;

public class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        Set[] knownLang = new Set[languages.length];
        for (int i = 0; i < languages.length; i++) {
            knownLang[i] = new HashSet<Integer>();
            for (int lang : languages[i]) {
                knownLang[i].add(lang);
            }
        }

        int result = Integer.MAX_VALUE;

        for (int lang = 1; lang <= n; lang++) {
            Set<Integer> needTeach = new HashSet<>();

            for (int[] pair : friendships) {
                int u = pair[0] - 1;
                int v = pair[1] - 1;

                if (!knownLang[u].contains(lang) && !knownLang[v].contains(lang)) {
                    if (!knownLang[u].contains(lang)) needTeach.add(u);
                    if (!knownLang[v].contains(lang)) needTeach.add(v);
                }
            }

            result = Math.min(result, needTeach.size());
        }

        return result;
    }
}
#include <iostream>
#include <vector>
#include <unordered_set>
#include <limits.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<unordered_set<int>> languages(m);
    vector<pair<int, int>> friendships;

    for (int i = 0; i < m; i++) {
        int t;
        cin >> t;
        for (int j = 0; j < t; j++) {
            int lang;
            cin >> lang;
            languages[i].insert(lang);
        }
    }

    int f;
    cin >> f;
    friendships.reserve(f);

    for (int i = 0; i < f; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        friendships.push_back({u, v});
    }

    int minTeach = INT_MAX;

    for (int lang = 1; lang <= n; lang++) {
        int teachCount = 0;
        unordered_set<int> needsTeaching;

        for (auto &pair : friendships) {
            int u = pair.first;
            int v = pair.second;

            if (languages[u].count(lang) == 0 && languages[v].count(lang) == 0) {
                if (languages[u].count(lang) == 0) needsTeaching.insert(u);
                if (languages[v].count(lang) == 0) needsTeaching.insert(v);
            }
        }

        teachCount = needsTeaching.size();
        minTeach = min(minTeach, teachCount);
    }

    cout << minTeach << endl;

    return 0;
}
function minimumTeachings(n, languages, friendships) {
    const languagesSet = languages.map(langs => new Set(langs));
    let minTeach = Infinity;

    for (let lang = 1; lang <= n; lang++) {
        const needTeaching = new Set();

        for (let [u, v] of friendships) {
            u -= 1;
            v -= 1;

            if (!languagesSet[u].has(lang) && !languagesSet[v].has(lang)) {
                if (!languagesSet[u].has(lang)) needTeaching.add(u);
                if (!languagesSet[v].has(lang)) needTeaching.add(v);
            }
        }

        minTeach = Math.min(minTeach, needTeaching.size);
    }

    return minTeach;
}
#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define MAX 501

int main() {
    int n, m;
    scanf("%d", &n);
    scanf("%d", &m);

    int languages[MAX][MAX] = {0};
    int friendships[m][2];
    bool canCommunicate[MAX][MAX] = {false};

    for (int i = 0; i < m; i++) {
        int k;
        scanf("%d", &k);
        for (int j = 0; j < k; j++) {
            int lang;
            scanf("%d", &lang);
            languages[i][lang] = 1;
        }
    }

    int f;
    scanf("%d", &f);
    for (int i = 0; i < f; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        friendships[i][0] = u - 1;
        friendships[i][1] = v - 1;
    }

    for (int i = 0; i < f; i++) {
        int u = friendships[i][0];
        int v = friendships[i][1];
        for (int l = 1; l <= n; l++) {
            if (languages[u][l] && languages[v][l])
                canCommunicate[u][v] = canCommunicate[v][u] = true;
        }
    }

    int minTeach = INT_MAX;

    for (int l = 1; l <= n; l++) {
        int teachCount = 0;

        for (int i = 0; i < f; i++) {
            int u = friendships[i][0];
            int v = friendships[i][1];

            if (!canCommunicate[u][v]) {
                if (!languages[u][l]) teachCount++;
                if (!languages[v][l]) teachCount++;
                canCommunicate[u][v] = true;
            }
        }

        if (teachCount < minTeach) minTeach = teachCount;

        for (int i = 0; i < f; i++) {
            int u = friendships[i][0];
            int v = friendships[i][1];
            canCommunicate[u][v] = false;
        }

        for (int i = 0; i < f; i++) {
            int u = friendships[i][0];
            int v = friendships[i][1];
            for (int k = 1; k <= n; k++) {
                if (languages[u][k] && languages[v][k])
                    canCommunicate[u][v] = canCommunicate[v][u] = true;
            }
        }
    }

    printf("%d", minTeach);

    return 0;
}
using System;
using System.Collections.Generic;

public class Solution {
    public int MinimumTeachings(int n, int[][] languages, int[][] friendships) {
        HashSet<int>[] langKnown = new HashSet<int>[languages.Length];
        for (int i = 0; i < languages.Length; i++) {
            langKnown[i] = new HashSet<int>(languages[i]);
        }

        int minTeach = int.MaxValue;

        for (int lang = 1; lang <= n; lang++) {
            HashSet<int> toTeach = new HashSet<int>();

            foreach (var pair in friendships) {
                int u = pair[0] - 1;
                int v = pair[1] - 1;

                if (!langKnown[u].Contains(lang) && !langKnown[v].Contains(lang)) {
                    if (!langKnown[u].Contains(lang)) toTeach.Add(u);
                    if (!langKnown[v].Contains(lang)) toTeach.Add(v);
                }
            }

            minTeach = Math.Min(minTeach, toTeach.Count);
        }

        return minTeach;
    }
}

The Python solution uses sets to handle known languages by each user. We iterate through each language, counting unfriended users who would need to learn the language to resolve communication gaps.

Complexity

Time Complexity: O(f * n * m) - Each potential teaching scenario is considered.
Space Complexity: O(m) - Using set to store distinct users requiring teaching per language.

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.
def minimumTeachings(n, languages, friendships):
    from collections import defaultdict

    know_lang = [set(l) for l in languages]

    min_teach = float('inf')

    for lang in range(1, n + 1):
        teaching_set = set()

        for u, v in friendships:
            u -= 1
            v -= 1

            if lang not in know_lang[u] and lang not in know_lang[v]:
                if lang not in know_lang[u]:
                    teaching_set.add(u)
                if lang not in knowlang[v]:
                    teaching_set.add(v)

        min_teach = min(min_teach, len(teaching_set))

    return min_teach
import java.util.*;

public class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        Set[] knowledgeMap = new HashSet[languages.length];

        for (int i = 0; i < languages.length; i++) {
            knowledgeMap[i] = new HashSet<Integer>();
            for (int lan : languages[i]) {
                knowledgeMap[i].add(lan);
            }
        }

        int minTeach = Integer.MAX_VALUE;

        for (int lan = 1; lan <= n; lan++) {
            Set<Integer> toTeach = new HashSet<Integer>();

            for (int[] pair : friendships) {
                int a = pair[0] - 1;
                int b = pair[1] - 1;

                if (!knowledgeMap[a].contains(lan) && !knowledgeMap[b].contains(lan)) {
                    if (!knowledgeMap[a].contains(lan)) toTeach.add(a);
                    if (!knowledgeMap[b].contains(lan)) toTeach.add(b);
                }
            }

            minTeach = Math.min(minTeach, toTeach.size());
        }

        return minTeach;
    }
}
#include <iostream>
#include <vector>
#include <unordered_set>
#include <limits.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<vector<int>> users(m);

    for (int i = 0; i < m; i++) {
        int l;
        cin >> l;
        users[i].resize(l);
        for (int j = 0; j < l; j++) {
            cin >> users[i][j];
        }
    }

    int f;
    cin >> f;
    vector<pair<int, int>> friendships;
    for (int i = 0; i < f; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        friendships.push_back({a, b});
    }

    int result = f;

    for (int l = 1; l <= n; l++) {
        unordered_set<int> needTeaching;
        for (auto &p : friendships) {
            int u = p.first;
            int v = p.second;

            bool canTalk = false;
            for (auto lang : users[u]) {
                if (lang == l) {
                    canTalk = true;
                    break;
                }
            }
            if (!canTalk) {
                for (auto lang : users[v]) {
                    if (lang == l) {
                        canTalk = true;
                        break;
                    }
                }
            }

            if (!canTalk) {
                if (users[u].end() == find(users[u].begin(), users[u].end(), l)) {
                    needTeaching.insert(u);
                }
                if (users[v].end() == find(users[v].begin(), users[v].end(), l)) {
                    needTeaching.insert(v);
                }
            }
        }

        result = min(result, int(needTeaching.size()));
    }

    cout << result << endl;

    return 0;
}
function minimumTeachings(n, languages, friendships) {
 let langSets = languages.map(arr => new Set(arr));
 let minTeachings = friendships.length;

 for (let lang = 1; lang <= n; lang++) {
   let requireTeachSet = new Set();

   for (let [u, v] of friendships) {
     u -= 1;
     v -= 1;

     if (!langSets[u].has(lang) && !langSets[v].has(lang)) {
       if (!langSets[u].has(lang)) requireTeachSet.add(u);
       if (!langSets[v].has(lang)) requireTeachSet.add(v);
     }
   }

   minTeachings = Math.min(minTeachings, requireTeachSet.size);
 }

 return minTeachings;
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX 501

int languages[MAX][MAX];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < m; i++) {
        int t;
        scanf("%d", &t);
        for (int j = 0; j < t; j++) {
            int lang;
            scanf("%d", &lang);
            languages[i][lang] = 1;
        }
    }

    int f;
    scanf("%d", &f);
    int minTeach = f;
    for (int lang = 1; lang <= n; lang++) {
        bool needsTeaching[MAX] = {false};
        int teachCount = 0;

        for (int i = 0; i < f; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            u--; v--;

            if (!languages[u][lang] && !languages[v][lang]) {
                if (!needsTeaching[u]) {
                    needsTeaching[u] = true;
                    teachCount++;
                }
                if (!needsTeaching[v]) {
                    needsTeaching[v] = true;
                    teachCount++;
                }
            }
        }
        if (teachCount < minTeach) minTeach = teachCount;
    }

    printf("%d", minTeach);
    return 0;
}
using System;
using System.Linq;
using System.Collections.Generic;

public class Solution {
    public int MinimumTeachings(int n, int[][] languages, int[][] friendships) {
        HashSet<int>[] languageProfs = languages.Select(l => new HashSet<int>(l)).ToArray();
        int minTeachings = friendships.Length;

        for (int lang = 1; lang <= n; lang++) {
            HashSet<int> mustTeach = new HashSet<int>();

            foreach (var pair in friendships) {
                int u = pair[0] - 1, v = pair[1] - 1;
                if (!languageProfs[u].Contains(lang) && !languageProfs[v].Contains(lang)) {
                    if (!languageProfs[u].Contains(lang)) mustTeach.Add(u);
                    if (!languageProfs[v].Contains(lang)) mustTeach.Add(v);
                }
            }

            minTeachings = Math.Min(minTeachings, mustTeach.Count);
        }

        return minTeachings;
    }
}

The Python setup considers graph coverage using unserved nodes pivoted upon acknowledged language sets cross-verifying partitions.

Complexity

Time Complexity: O(f * n * m) - Compacts through all possibilities jest among friendships.
Space Complexity: An auxiliary set preserves unchecked relations per attempt.

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.

function minimumTeachings(n: number, languages: number[][], friendships: number[][]): number {
    function check(u: number, v: number): boolean {
        for (const x of languages[u - 1]) {
            for (const y of languages[v - 1]) {
                if (x === y) {
                    return true;
                }
            }
        }
        return false;
    }

    const s = new Set<number>();
    for (const [u, v] of friendships) {
        if (!check(u, v)) {
            s.add(u);
            s.add(v);
        }
    }

    const cnt = new Map<number, number>();
    for (const u of s) {
        for (const l of languages[u - 1]) {
            cnt.set(l, (cnt.get(l) || 0) + 1);
        }
    }

    return s.size - Math.max(0, ...cnt.values());
}
func minimumTeachings(n int, languages [][]int, friendships [][]int) int {
	check := func(u, v int) bool {
		for _, x := range languages[u-1] {
			for _, y := range languages[v-1] {
				if x == y {
					return true
				}
			}
		}
		return false
	}
	s := map[int]bool{}
	for _, e := range friendships {
		u, v := e[0], e[1]
		if !check(u, v) {
			s[u], s[v] = true, true
		}
	}
	if len(s) == 0 {
		return 0
	}
	cnt := make([]int, n+1)
	for u := range s {
		for _, l := range languages[u-1] {
			cnt[l]++
		}
	}
	return len(s) - slices.Max(cnt)
}
use std::collections::{HashSet, HashMap};

impl Solution {
    pub fn minimum_teachings(n: i32, languages: Vec<Vec<i32>>, friendships: Vec<Vec<i32>>) -> i32 {
        fn check(u: usize, v: usize, languages: &Vec<Vec<i32>>) -> bool {
            for &x in &languages[u - 1] {
                for &y in &languages[v - 1] {
                    if x == y {
                        return true;
                    }
                }
            }
            false
        }

        let mut s: HashSet<usize> = HashSet::new();
        for edge in friendships.iter() {
            let u = edge[0] as usize;
            let v = edge[1] as usize;
            if !check(u, v, &languages) {
                s.insert(u);
                s.insert(v);
            }
        }

        let mut cnt: HashMap<i32, i32> = HashMap::new();
        for &u in s.iter() {
            for &l in &languages[u - 1] {
                *cnt.entry(l).or_insert(0) += 1;
            }
        }

        let mx = cnt.values().cloned().max().unwrap_or(0);
        (s.len() as i32) - mx
    }
}
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) - Each potential teaching scenario is considered.
Space Complexity: O(m) - Using set to store distinct users requiring teaching per language.

Approach 2: Bipartite Graph Optimization

Time Complexity: O(f * n * m) - Compacts through all possibilities jest among friendships.
Space Complexity: An auxiliary set preserves unchecked relations per attempt.

Simulation + Statistics–

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

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.

Comments

Now write it yourselfClose this page and solve Minimum Number of People to Teach in the editor, without looking.
Practise Minimum Number of People to Teach