Minimum number of people to teach

Array Hash Table Greedy

67.7% acceptance

Feb 25, 2026

716

560

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 ith user knows, and friendships[i] = [ui, vi] denotes a friendship between the users ui 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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::HashSet;

impl Solution {
  pub fn minimum_teachings(n: i32, languages: Vec<Vec<i32>>, friendships: Vec<Vec<i32>>) -> i32 {
    let _m = languages.len();
    // Build set of languages for each user (1-indexed)
    let lang_sets: Vec<HashSet<i32>> = languages.iter().map(|l| l.iter().cloned().collect()).collect();

    // Find pairs of friends that don't share a common language
    let incompatible: Vec<(usize, usize)> = friendships.iter()
      .filter_map(|f| {
        let u = f[0] as usize - 1;
        let v = f[1] as usize - 1;
        if lang_sets[u].intersection(&lang_sets[v]).next().is_none() {
          Some((u, v))
        } else {
          None
        }
      })
      .collect();

    if incompatible.is_empty() { return 0; }

    let mut best = i32::MAX;
    for lang in 1..=n {
      // Count users in incompatible pairs that don't know this language
      let mut to_teach: HashSet<usize> = HashSet::new();
      for &(u, v) in &incompatible {
        if !lang_sets[u].contains(&lang) { to_teach.insert(u); }
        if !lang_sets[v].contains(&lang) { to_teach.insert(v); }
      }
      best = best.min(to_teach.len() as i32);
    }
    best
  }
}