Created
September 10, 2025 20:18
-
-
Save SuryaPratapK/935ae89dbee09b30b8353c4fbe0d1ff7 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| bool cantTalk(const unordered_set<int>& s1, const unordered_set<int>& s2) { | |
| for (int lang1 : s1) | |
| if (s2.count(lang1)) return false; | |
| return true; | |
| } | |
| public: | |
| int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) { | |
| int m = languages.size(); | |
| // STEP-1: person -> languages (1-based indexing for persons) | |
| vector<unordered_set<int>> friend_lang(m + 1); | |
| for (int i = 1; i <= m; ++i) { | |
| for (int language : languages[i - 1]) | |
| friend_lang[i].insert(language); | |
| } | |
| // STEP-2: frequency of each language among distinct "bad" people | |
| vector<int> lang_freq(n + 1, 0); | |
| vector<char> seen(m + 1, 0); // whether a person was counted already | |
| vector<int> cant_talk_friends; // distinct people in failing friendships | |
| cant_talk_friends.reserve(m); | |
| for (const auto& friendship : friendships) { | |
| int a = friendship[0], b = friendship[1]; | |
| if (cantTalk(friend_lang[a], friend_lang[b])) { | |
| if (!seen[a]) { | |
| seen[a] = 1; | |
| for (int la : friend_lang[a]) ++lang_freq[la]; | |
| cant_talk_friends.push_back(a); | |
| } | |
| if (!seen[b]) { | |
| seen[b] = 1; | |
| for (int la : friend_lang[b]) ++lang_freq[la]; | |
| cant_talk_friends.push_back(b); | |
| } | |
| } | |
| } | |
| if (cant_talk_friends.empty()) return 0; // nothing to teach | |
| // STEP-3: pick language known by maximum bad people | |
| int max_known = 0; | |
| int best_lang = 1; | |
| for (int la = 1; la <= n; ++la) { | |
| if (lang_freq[la] > max_known) { | |
| max_known = lang_freq[la]; | |
| best_lang = la; | |
| } | |
| } | |
| // STEP-4: count how many bad people still need to be taught best_lang | |
| int teach_count = 0; | |
| for (int p : cant_talk_friends) | |
| if (!friend_lang[p].count(best_lang)) | |
| ++teach_count; | |
| return teach_count; | |
| } | |
| }; | |
| /* | |
| //JAVA | |
| class Solution { | |
| private boolean cantTalk(Set<Integer> s1, Set<Integer> s2) { | |
| // iterate over smaller for slight optimization | |
| if (s1.size() > s2.size()) { | |
| Set<Integer> tmp = s1; s1 = s2; s2 = tmp; | |
| } | |
| for (int lang : s1) { | |
| if (s2.contains(lang)) return false; | |
| } | |
| return true; | |
| } | |
| // LeetCode signature: n = number of languages, languages = person -> list of languages (1-indexed persons), | |
| // friendships as int[][] where each friendship is [a, b] | |
| public int minimumTeachings(int n, List<List<Integer>> languages, int[][] friendships) { | |
| int m = languages.size(); // number of people | |
| // person -> languages (1-based indexing for persons) | |
| @SuppressWarnings("unchecked") | |
| Set<Integer>[] friendLang = new HashSet[m + 1]; | |
| for (int i = 1; i <= m; ++i) { | |
| friendLang[i] = new HashSet<>(languages.get(i - 1)); | |
| } | |
| // frequency of each language among distinct "bad" people | |
| int[] langFreq = new int[n + 1]; | |
| boolean[] seen = new boolean[m + 1]; | |
| List<Integer> cantTalkFriends = new ArrayList<>(); | |
| for (int[] fr : friendships) { | |
| int a = fr[0], b = fr[1]; | |
| if (cantTalk(friendLang[a], friendLang[b])) { | |
| if (!seen[a]) { | |
| seen[a] = true; | |
| for (int la : friendLang[a]) langFreq[la]++; | |
| cantTalkFriends.add(a); | |
| } | |
| if (!seen[b]) { | |
| seen[b] = true; | |
| for (int la : friendLang[b]) langFreq[la]++; | |
| cantTalkFriends.add(b); | |
| } | |
| } | |
| } | |
| if (cantTalkFriends.isEmpty()) return 0; | |
| // pick language known by maximum bad people | |
| int bestLang = 1; | |
| int maxKnown = 0; | |
| for (int la = 1; la <= n; ++la) { | |
| if (langFreq[la] > maxKnown) { | |
| maxKnown = langFreq[la]; | |
| bestLang = la; | |
| } | |
| } | |
| // count how many bad people still need to be taught bestLang | |
| int teachCount = 0; | |
| for (int p : cantTalkFriends) { | |
| if (!friendLang[p].contains(bestLang)) teachCount++; | |
| } | |
| return teachCount; | |
| } | |
| } | |
| #Python | |
| from typing import List, Set | |
| class Solution: | |
| def cant_talk(self, s1: Set[int], s2: Set[int]) -> bool: | |
| # iterate smaller set for a small optimization | |
| if len(s1) > len(s2): | |
| s1, s2 = s2, s1 | |
| for lang in s1: | |
| if lang in s2: | |
| return False | |
| return True | |
| def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int: | |
| m = len(languages) | |
| # person -> set of languages (1-based) | |
| friend_lang = [set() for _ in range(m + 1)] | |
| for i in range(1, m + 1): | |
| friend_lang[i] = set(languages[i - 1]) | |
| lang_freq = [0] * (n + 1) | |
| seen = [False] * (m + 1) | |
| cant_talk_friends = [] | |
| for a, b in friendships: | |
| if self.cant_talk(friend_lang[a], friend_lang[b]): | |
| if not seen[a]: | |
| seen[a] = True | |
| for la in friend_lang[a]: | |
| lang_freq[la] += 1 | |
| cant_talk_friends.append(a) | |
| if not seen[b]: | |
| seen[b] = True | |
| for la in friend_lang[b]: | |
| lang_freq[la] += 1 | |
| cant_talk_friends.append(b) | |
| if not cant_talk_friends: | |
| return 0 | |
| # pick language known by maximum bad people | |
| best_lang = max(range(1, n + 1), key=lambda x: lang_freq[x]) | |
| # count how many bad people still need to be taught best_lang | |
| teach_count = sum(1 for p in cant_talk_friends if best_lang not in friend_lang[p]) | |
| return teach_count | |
| */ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment