Java HashMap
Intuition\n1. We need to find out which friends can already communicate so that we don\'t need to calculate the language teaching for them.\n2. For every langua
# Intuition\n1. We need to find out which friends can already communicate so that we don\'t need to calculate the language teaching for them.\n2. For every language , iterate through the friendship array and check if we need to teach the language to both the friends to be able to communicate.\n3. At the end , compare which language was needed to be taught to the least number of users and return.\n# Approach\n1. Create a map for user to set of languages to be able to fetch a language for a user in O(1)\n2. Create a boolean array specifying if the friend pair already has a common language.\n3. For every language check , how many people need to be taught that language. Note the count, and after every iteration, update the count if it is less than the count of previous language\n\n# Complexity\n- Time complexity:\nFor creating the map, if the number of users are m and maximum number of language spoken by a user is n.\nThe time complexity is O(m*n)\nIf total Friendships are k , then creating the boolean array is \nO(k*n)\nIf there are l languages, we are iterating l times * number of friendships k times. O(l*k)\nTotal time complexity is O(m*n)+O(k*n)+O(l*k)\n\n- Space complexity:\nFor creating the map, if the number of users are m and maximum number of language spoken by a user is n.\nThe space complexity is O(m*n)\nIf total Friendships are k , then space complexity of boolean array is \nO(k)\nThe size of teach set at the end cannot be more than that of number of users m thus space complexity is O(m)\nTotal space complexity is O(m*n)+O(k)+O(m) which will be equal to O(m*n) as we can drop the other smaller k and m.\n\n\n\n# Code\n```\nclass Solution {\n    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {\n        //create a map for user to set of languages to be able to fetch a language for a user in O(1)\n        Map<Integer,Set<Integer>> userToLang = new HashMap<>();\n        for(int i=0;i<languages.length;i++){\n            Set<Integer> set = new HashSet<>();\n            for(int lang:languages[i]){\n                set.add(lang);\n            }\n            userToLang.put(i+1,set);\n        }\n        //Create a boolean array specifying if the friend pair already has a common language\n        boolean[] canCommunicate = new boolean[friendships.length];\n        Arrays.fill(canCommunicate,false);\n        for(int i=0;i<friendships.length;i++){\n            int f1 = friendships[i][0];//friend 1\n            int f2 = friendships[i][1];//friend2\n            //check if friend 1 speaks the same language as friend2\n            for(int lang:userToLang.get(f1)){\n                if(userToLang.get(f2).contains(lang)){\n                    canCommunicate[i]=true;\n                    break;\n                }\n            }\n        }\n        //For every language check , how many people need to be taught that language\n        //note the count , and after every iteration, update the count if it is less than the count \n        //of previous language\n        int totalUsers = languages.length;\n        for(int i=1;i<=n;i++){\n            Set<Integer> teach = new HashSet<>();\n            for(int j=0;j<friendships.length;j++){\n                if(canCommunicate[j])continue;\n                //check if we need to teach the language to f1 and f2\n                int friend1 = friendships[j][0];\n                int friend2 = friendships[j][1];\n                if(!userToLang.get(friend1).contains(i)) teach.add(friend1);\n                if(!userToLang.get(friend2).contains(i)) teach.add(friend2);\n            }\n            totalUsers=Math.min(totalUsers, teach.size());\n        }\n        return totalUsers;   \n    }\n}\n\n\n```
['Java']