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 lang

minimumTeachings.js

/**
 * @param {number} n
 * @param {number[][]} languages
 * @param {number[][]} friendships
 * @return {number}
 */
var minimumTeachings = function(n, languages, friendships) {
    // 1) Convert each user's language list to a Set for 0(1) checks.
    // We'll store with 1-based alignment: user i => index i (ignore index 0).
    const userLangs = Array(languages.length + 1);
    for (let i = 0; i < languages.length; i++) {
        userLangs[i + 1] = new Set(languages[i]); // users are 1-based
    }

    // 2) Find "problem" friendships: pairs without a common language.
    const candidates = new Set(); // users who might need teaching
    for (const [u, v] of friendships) {
        if (!haveCommonLanguage(userLangs[u], userLangs[v])) {
            candidates.add(u);
            candidates.add(v);
        }
    }

    // 3) If there are no problem pairs, no teaching needed.
    if (candidates.size === 0) return 0;

    // 4) For each language L, count how many candidate users don't know L.
    // We'll compute: needTeachCount[L] for L in [1..n].
    const needTeachCount = Array(n + 1).fill(0);
    for (const user of candidates) {
        // For each language L from 1..n, increment if user lacks L.
        // If n is large, consider an optimization below.
        for (let L = 1; L <= n; L++) {
            if (!userLangs[user].has(L)) {
                needTeachCount[L]++;
            }
        }
    }

    // 5) Answer is the minimum across all languages.
    let ans = Infinity;
    for (let L = 1; L <= n; L++) {
        ans = Math.min(ans, needTeachCount[L]);
    }

    return ans;
};

// Helper: check if two sets intersect.
function haveCommonLanguage(setA, setB) {
    // Iterate over the smaller set for efficiency.
    if (setA.size > setB.size) [setA, setB] = [setB, setA];
    for (const x of setA) {
        if (setB.has(x)) return true;
    }
    return false;
}