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.

Examples

Example 1

1
2
3

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

1
2
3

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

Solution

Method 1 – Greedy Language Selection

Intuition

For each friendship, if the two users do not share a language, we must teach one language to at least one of them. To minimize the number of people to teach, try each language and count how many users need to learn it so all friendships are covered.

Approach

  1. For each friendship, check if the two users share a language. If not, add both to a set of candidates.
  2. For each language, count how many candidates do not know it.
  3. The answer is the minimum such count over all languages.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <vector>
#include <unordered_set>
using namespace std;
class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        int m = languages.size();
        vector<unordered_set<int>> knows(m);
        for (int i = 0; i < m; ++i)
            for (int l : languages[i]) knows[i].insert(l);
        unordered_set<int> candidates;
        for (auto& f : friendships) {
            int u = f[0] - 1, v = f[1] - 1;
            bool ok = false;
            for (int l : knows[u]) if (knows[v].count(l)) { ok = true; break; }
            if (!ok) { candidates.insert(u); candidates.insert(v); }
        }
        int res = m;
        for (int l = 1; l <= n; ++l) {
            int cnt = 0;
            for (int u : candidates) if (!knows[u].count(l)) cnt++;
            res = min(res, cnt);
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

func minimumTeachings(n int, languages [][]int, friendships [][]int) int {
    m := len(languages)
    knows := make([]map[int]struct{}, m)
    for i := range knows {
        knows[i] = make(map[int]struct{})
        for _, l := range languages[i] {
            knows[i][l] = struct{}{}
        }
    }
    candidates := map[int]struct{}{}
    for _, f := range friendships {
        u, v := f[0]-1, f[1]-1
        ok := false
        for l := range knows[u] {
            if _, found := knows[v][l]; found {
                ok = true
                break
            }
        }
        if !ok {
            candidates[u] = struct{}{}
            candidates[v] = struct{}{}
        }
    }
    res := m
    for l := 1; l <= n; l++ {
        cnt := 0
        for u := range candidates {
            if _, found := knows[u][l]; !found {
                cnt++
            }
        }
        if cnt < res {
            res = cnt
        }
    }
    return res
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;
class Solution {
    public int minimumTeachings(int n, List<List<Integer>> languages, List<List<Integer>> friendships) {
        int m = languages.size();
        List<Set<Integer>> knows = new ArrayList<>();
        for (List<Integer> lang : languages) knows.add(new HashSet<>(lang));
        Set<Integer> candidates = new HashSet<>();
        for (List<Integer> f : friendships) {
            int u = f.get(0) - 1, v = f.get(1) - 1;
            boolean ok = false;
            for (int l : knows.get(u)) if (knows.get(v).contains(l)) { ok = true; break; }
            if (!ok) { candidates.add(u); candidates.add(v); }
        }
        int res = m;
        for (int l = 1; l <= n; ++l) {
            int cnt = 0;
            for (int u : candidates) if (!knows.get(u).contains(l)) cnt++;
            res = Math.min(res, cnt);
        }
        return res;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun minimumTeachings(n: Int, languages: List<List<Int>>, friendships: List<List<Int>>): Int {
        val m = languages.size
        val knows = languages.map { it.toSet() }
        val candidates = mutableSetOf<Int>()
        for (f in friendships) {
            val u = f[0] - 1; val v = f[1] - 1
            if (knows[u].intersect(knows[v]).isEmpty()) {
                candidates.add(u); candidates.add(v)
            }
        }
        var res = m
        for (l in 1..n) {
            var cnt = 0
            for (u in candidates) if (!knows[u].contains(l)) cnt++
            res = minOf(res, cnt)
        }
        return res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def minimumTeachings(self, n: int, languages: list[list[int]], friendships: list[list[int]]) -> int:
        knows = [set(l) for l in languages]
        candidates = set()
        for u, v in friendships:
            u -= 1; v -= 1
            if knows[u].isdisjoint(knows[v]):
                candidates.add(u); candidates.add(v)
        res = len(languages)
        for l in range(1, n + 1):
            cnt = sum(1 for u in candidates if l not in knows[u])
            res = min(res, cnt)
        return res
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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();
        let knows: Vec<HashSet<i32>> = languages.iter().map(|l| l.iter().copied().collect()).collect();
        let mut candidates = HashSet::new();
        for f in friendships {
            let u = f[0] - 1; let v = f[1] - 1;
            if knows[u].is_disjoint(&knows[v]) {
                candidates.insert(u as i32); candidates.insert(v as i32);
            }
        }
        let mut res = m as i32;
        for l in 1..=n {
            let mut cnt = 0;
            for &u in &candidates {
                if !knows[u as usize].contains(&l) { cnt += 1; }
            }
            res = res.min(cnt);
        }
        res
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    minimumTeachings(n: number, languages: number[][], friendships: number[][]): number {
        const m = languages.length;
        const knows = languages.map(l => new Set(l));
        const candidates = new Set<number>();
        for (const [u, v] of friendships) {
            const u0 = u - 1, v0 = v - 1;
            const ok = [...knows[u0]].some(l => knows[v0].has(l));
            if (!ok) { candidates.add(u0); candidates.add(v0); }
        }
        let res = m;
        for (let l = 1; l <= n; ++l) {
            let cnt = 0;
            for (const u of candidates) if (!knows[u].has(l)) cnt++;
            res = Math.min(res, cnt);
        }
        return res;
    }
}

Complexity

  • ⏰ Time complexity: O(F * L * C) — F = number of friendships, L = number of languages, C = number of candidates.
  • 🧺 Space complexity: O(M + F) — M = number of users, F = number of friendships.