1733: Minimum-Number-of-People-to-Teach
Medium

table of contents

Since we can only choose ONE language to teach so that all friends can communicate, and our goal is to minimize the number of users who need to learn it, it makes sense to first identify ALL users who have communication issues with their friends. Then, we should select the language that the largest number of these users already know, so we have to teach it to as few people as possible.

First, we identify the friendships where both users are unable to communicate with each other, and then we add those users to an unordered_set.

for (vector<int>& friends : friendships) {
    possibleLanguages.clear();
    isCommunicationPossible = false;
    for (int& l : languages[friends[0] - 1]) {
        possibleLanguages[l] = 1; 
    }
    for (int& l : languages[friends[1] - 1]) {
        if (possibleLanguages[l] == 1) {
            isCommunicationPossible = true;
            break;
        }
    }

    if (!isCommunicationPossible) {
        noCommunication.insert(friends[0] - 1);
        noCommunication.insert(friends[1] - 1);
    }
}

Then, we iterate through the set and add all up all the languages everyone can speak.

vector<int> languageCount(n, 0);
for (auto& f : noCommunication) {
    for (int& l : languages[f]) {
        ++languageCount[l-1];
    }
}

Finally, we find the language with the maximum count, and subtract it from the total number of users with communication issues to get the minimum number of people we need to teach.

int mx = 0;
for (int& l : languageCount) {
    mx = max(mx, l);
}

return noCommunication.size() - mx;

code

class Solution {
public:
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        unordered_set<int> noCommunication;
        unordered_map<int, int> possibleLanguages;
        bool isCommunicationPossible;
        for (vector<int>& friends : friendships) {
            possibleLanguages.clear();
            isCommunicationPossible = false;
            for (int& l : languages[friends[0] - 1]) {
                possibleLanguages[l] = 1; 
            }
            for (int& l : languages[friends[1] - 1]) {
                if (possibleLanguages[l] == 1) {
                    isCommunicationPossible = true;
                    break;
                }
            }

            if (!isCommunicationPossible) {
                noCommunication.insert(friends[0] - 1);
                noCommunication.insert(friends[1] - 1);
            }
        }

        vector<int> languageCount(n, 0);
        for (auto& f : noCommunication) {
            for (int& l : languages[f]) {
                ++languageCount[l-1];
            }
        }

        int mx = 0;
        for (int& l : languageCount) {
            mx = max(mx, l);
        }

        return noCommunication.size() - mx;
    }
};

complexity

time taken