Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1733.html

1733. Minimum Number of People to Teach

Level

Medium

Description

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 v_i.

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

Solution

First, obtain each user’s languages. Then for each friendship, check whether the friends can communicate with each other. Only consider the friends that cannot communicate with each other. For such friendships, loop over all languages and find the language such that the minimum number of people need to be taught.

  • class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        Map<Integer, Set<Integer>> languagesMap = new HashMap<Integer, Set<Integer>>();
        int m = languages.length;
        for (int i = 0; i < m; i++) {
            int index = i + 1;
            int[] language = languages[i];
            Set<Integer> set = new HashSet<Integer>();
            for (int num : language)
                set.add(num);
            languagesMap.put(index, set);
        }
        List<int[]> friendshipsList = new ArrayList<int[]>();
        int pairs = friendships.length;
        for (int i = 0; i < pairs; i++) {
            int[] friendship = friendships[i];
            int user1 = friendship[0], user2 = friendship[1];
            Set<Integer> set1 = new HashSet<Integer>(languagesMap.getOrDefault(user1, new HashSet<Integer>()));
            Set<Integer> set2 = new HashSet<Integer>(languagesMap.getOrDefault(user2, new HashSet<Integer>()));
            set1.retainAll(set2);
            if (set1.size() == 0)
                friendshipsList.add(friendship);
        }
        Set<Integer> candidates = new HashSet<Integer>();
        Set<Integer> usersSet = new HashSet<Integer>();
        for (int[] friendship : friendshipsList) {
            int user1 = friendship[0], user2 = friendship[1];
            Set<Integer> set1 = languagesMap.getOrDefault(user1, new HashSet<Integer>());
            Set<Integer> set2 = languagesMap.getOrDefault(user2, new HashSet<Integer>());
            candidates.addAll(set1);
            candidates.addAll(set2);
            usersSet.add(user1);
            usersSet.add(user2);
        }
        if (candidates.isEmpty())
            return 0;
        int minTeach = Integer.MAX_VALUE;
        for (int candidate : candidates) {
            int teach = 0;
            for (int user : usersSet) {
                if (!languagesMap.getOrDefault(user, new HashSet<Integer>()).contains(candidate))
                    teach++;
            }
            minTeach = Math.min(minTeach, teach);
        }
        return minTeach;
    }
}

############

class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        Set<Integer> s = new HashSet<>();
        for (var e : friendships) {
            int u = e[0], v = e[1];
            if (!check(u, v, languages)) {
                s.add(u);
                s.add(v);
            }
        }
        if (s.isEmpty()) {
            return 0;
        }
        int[] cnt = new int[n + 1];
        for (int u : s) {
            for (int l : languages[u - 1]) {
                ++cnt[l];
            }
        }
        int mx = 0;
        for (int v : cnt) {
            mx = Math.max(mx, v);
        }
        return s.size() - mx;
    }

    private boolean check(int u, int v, int[][] languages) {
        for (int x : languages[u - 1]) {
            for (int y : languages[v - 1]) {
                if (x == y) {
                    return true;
                }
            }
        }
        return false;
    }
}

  • // OJ: https://leetcode.com/problems/minimum-number-of-people-to-teach/
// Time: O((L + F) * N)
// Space: O(LN)
class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& L, vector<vector<int>>& F) {
        int M = L.size();
        vector<unordered_set<int>> G(M); // people to language
        for (int i = 0; i < M; ++i) {
            for (int n : L[i]) G[i].insert(n - 1);
        }
        unordered_set<int> s;
        for (auto &f : F) {
            int a = f[0] - 1, b = f[1] - 1, i;
            for (i = 0; i < n; ++i) {
                if (G[a].count(i) && G[b].count(i)) break;
            }
            if (i == n) s.insert(a), s.insert(b);
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; ++i) { // try each language
            int cnt = 0;
            for (int p : s) {
                cnt += G[p].count(i) == 0; 
            }
            ans = min(ans, cnt);
        }
        return ans;
    }
};

  • class Solution:
    def minimumTeachings(
        self, n: int, languages: List[List[int]], friendships: List[List[int]]
    ) -> int:
        def check(u, v):
            for x in languages[u - 1]:
                for y in languages[v - 1]:
                    if x == y:
                        return True
            return False

        s = set()
        for u, v in friendships:
            if not check(u, v):
                s.add(u)
                s.add(v)
        cnt = Counter()
        for u in s:
            for l in languages[u - 1]:
                cnt[l] += 1
        return len(s) - max(cnt.values(), default=0)

############

# 1733. Minimum Number of People to Teach
# https://leetcode.com/problems/minimum-number-of-people-to-teach/

class Solution:
    def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]):
        languages = [set(l) for l in languages]
        
        dontspeak = set()
        for u,v in friendships:
            u -= 1
            v -= 1
            
            if languages[u] & languages[v]: continue
            
            dontspeak.add(u)
            dontspeak.add(v)
        
        speak = Counter()
        for p in dontspeak:
            for l in languages[p]:
                speak[l] += 1
        
        return 0 if len(dontspeak) == 0 else len(dontspeak) - max(speak.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]++
		}
	}
	mx := 0
	for _, v := range cnt {
		mx = max(mx, v)
	}
	return len(s) - mx
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

All Problems

All Solutions