O(M*N) Greedy solution using Set
\n# Complexity\n- Time complexity:\nO(M*N)\n\n- Space complexity:\nO(M)\n\n# Code\n\nfunction minimumTeachings(n: number, languages: number[][], friendships: nu
\n# Complexity\n- Time complexity:\nO(M*N)\n\n- Space complexity:\nO(M)\n\n# Code\n```\nfunction minimumTeachings(n: number, languages: number[][], friendships: number[][]): number {\n    function createFriendsLanguageSets() {\n      let friendsLanguageSets: Set<number>[] = new Array(1);\n      for (let i = 0; i < languages.length; i++) {\n        let fLangs = new Set<number>();\n        languages[i].forEach(x => fLangs.add(x));\n        friendsLanguageSets.push(fLangs);\n      }\n      return friendsLanguageSets;\n\n    }\n\n    function findFriendsWithNoLanguage(languages: number[][], friendships: number[][], friendsLanguageSets: Set<number>[]) {\n      let friendsWithNoLanguage: number[][] = new Array(1);\n      for (let i = 0; i < friendships.length; i++) {\n        let f1Langs = friendsLanguageSets[friendships[i][0]]\n        let f2Langs = friendsLanguageSets[friendships[i][1]];\n\n        let canTalk = false;\n        for (let lang of f1Langs.keys()) {\n          if (f2Langs.has(lang)) {\n            canTalk = true;\n            break;\n          }\n        }\n        if (!canTalk) {\n          friendsWithNoLanguage.push(friendships[i]);\n        }\n      }\n      return friendsWithNoLanguage;\n    }\n\n    let friendsLanguageSets = createFriendsLanguageSets();\n    let brokenFriendships = findFriendsWithNoLanguage(languages, friendships, friendsLanguageSets);\n\n    let i = 1;\n    let min = Number.MAX_VALUE;\n    while (i <= n) {\n      let count = 0;\n      let visitedFrinds = new Set<number>();\n      for (let j = 1; j < brokenFriendships.length; j++) {\n        let f1 = brokenFriendships[j][0];\n        let f2 = brokenFriendships[j][1];\n        if (!friendsLanguageSets[f1].has(i) && !visitedFrinds.has(f1)) {\n          visitedFrinds.add(f1);\n          count++;\n        }\n        if (!friendsLanguageSets[f2].has(i) && !visitedFrinds.has(f2)) {\n          visitedFrinds.add(f2);\n          count++;\n        }\n      }\n      if (count < min) {\n        min = count;\n      }\n      i++;\n    }\n    return min;\n};\n```
['TypeScript']