Beats 100%, Hash Table, O(n + m)
Intuition\nCreate a list of users\' pairs which need to learn a new language.\n\n# Approach\nAt first create new dictionary dicLang with a user as a key and a s
# Intuition\nCreate a list of users\' pairs which need to learn a new language.\n\n# Approach\nAt first create new dictionary `dicLang` with a user as a key and a set of user\'s languages as a value:\n```\nvar dicLang = CreateDicOfLanguages(languages);\n```\nThe create a list of users who need to learn a new language:\n```\nvar set = new HashSet<int>();\nfor (int i = 0; i < friendships.Length; i++)\n{\n    if (dicLang[friendships[i][0]].Intersect(dicLang[friendships[i][1]]).Count() == 0)\n    {\n        set.Add(friendships[i][0]);\n        set.Add(friendships[i][1]);\n    }\n}\n```\nAfter that find the language with the naximum number of speakers:\n```\nvar maxLang = 0;\nforeach (var item in set)\n{\n    foreach (var lang in dicLang[item])\n    {\n        if (!dic.ContainsKey(lang)) dic.Add(lang, 0);\n        dic[lang]++;\n        maxLang = Math.Max(maxLang, dic[lang]);\n    }\n}\n```\nFinally caclulate the result:\n```\nvar rs = set.Count - maxLang;\nreturn rs;\n```\n\n# Complexity\n- Time complexity:\n$$O(k + m)$$, where m is the len(languages) and k is the len(friendships)\n\n- Space complexity:\n$$O(k + m)$$, where m is the len(languages) and k is the len(friendships)\n\n# Code\n```\npublic class Solution {\n    public int MinimumTeachings(int n, int[][] languages, int[][] friendships) {\n        var dicLang = CreateDicOfLanguages(languages);\n        var set = new HashSet<int>();\n        for (int i = 0; i < friendships.Length; i++)\n        {\n            if ((dicLang[friendships[i][0]].Intersect(dicLang[friendships[i][1]])).Count() == 0)\n            {\n                set.Add(friendships[i][0]);\n                set.Add(friendships[i][1]);\n            }\n        }\n        var dic = new Dictionary<int, int>();\n        var maxLang = 0;\n        foreach (var item in set)\n        {\n            foreach (var lang in dicLang[item])\n            {\n                if (!dic.ContainsKey(lang)) dic.Add(lang, 0);\n                dic[lang]++;\n                maxLang = Math.Max(maxLang, dic[lang]);\n            }\n        }\n        var rs = set.Count - maxLang;\n        return rs;\n    }\n    private Dictionary<int, HashSet<int>> CreateDicOfLanguages(int[][] languages)\n    {\n        var rs = new Dictionary<int, HashSet<int>>();\n        for (int i = 0; i < languages.Length; i++)\n        {\n            rs.Add(i + 1, new HashSet<int>(languages[i]));\n        }\n        return rs;\n    }\n}\n```
['Hash Table', 'C#']