LeetCode 1733: Minimum Number of People to Teach
Problem Description
Explanation:
To solve this problem, we can iterate through all possible languages and for each language, calculate the number of users we need to teach in order to make all friends communicate with each other. We can do this by creating a graph where each node represents a user and an edge exists between two nodes if they are friends and do not share the common language.
We will then iterate through all languages and for each language, count the number of users we need to teach in order to make all friends communicate with each other. We will keep track of the minimum number of users needed. Finally, we return the minimum number of users needed.
Algorithm:
- Create a graph representing friendships where nodes are users and edges are friendships.
- Iterate through each language.
- For each language, calculate the number of users needed to be taught.
- Keep track of the minimum number of users needed.
- Return the minimum number of users needed.
Time Complexity: O(n^2 * m) where n is the number of languages and m is the number of friendships.
Space Complexity: O(n^2) for storing the graph.
:
Solutions
class Solution {
public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
Set<Integer>[] langSet = new Set[n + 1];
for (int i = 0; i < languages.length; i++) {
langSet[i + 1] = new HashSet<>();
for (int lang : languages[i]) {
langSet[i + 1].add(lang);
}
}
boolean[] needTeach = new boolean[friendships.length];
for (int i = 0; i < friendships.length; i++) {
int u = friendships[i][0];
int v = friendships[i][1];
boolean canCommunicate = false;
for (int lang : langSet[u]) {
if (langSet[v].contains(lang)) {
canCommunicate = true;
break;
}
}
if (!canCommunicate) {
needTeach[i] = true;
}
}
int minTeach = Integer.MAX_VALUE;
for (int lang = 1; lang <= n; lang++) {
Set<Integer> usersToTeach = new HashSet<>();
for (int i = 0; i < friendships.length; i++) {
if (needTeach[i]) {
if (!langSet[friendships[i][0]].contains(lang)) {
usersToTeach.add(friendships[i][0]);
}
if (!langSet[friendships[i][1]].contains(lang)) {
usersToTeach.add(friendships[i][1]);
}
}
}
minTeach = Math.min(minTeach, usersToTeach.size());
}
return minTeach;
}
}Loading editor...