Leetcode 1733 - Minimum Number of People to Teach

Subscribe Send me a message

#leetcode

Description

On a social network consisting of m users and some friendships between users, two users can communicate with each other if they know a common language.

You are given an integer n, an array languages, and an array friendships where:

There are n languages numbered 1 through n,
languages[i] is the set of languages the \(i^{th}\) user knows, and
friendships[i] = [\(u_i\), \(v_i\)] denotes a friendship between the user \(u_i\) and \(v_i\).

You can choose one language and teach it to some users so that all friends can communicate with each other. Return the minimum number of users you need to teach.

Note that friendships are not transitive, meaning if x is a friend of y and y is a friend of z, this doesn't guarantee that x is a friend of z.

Example 1:

Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]
Output: 1
Explanation: You can either teach user 1 the second language or user 2 the first language.

Example 2:

Input: n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]]
Output: 2
Explanation: Teach the third language to users 1 and 2, yielding two users to teach.

Analysis

We make the following observations:

If two friends have a common language, then we can ignore them in the calculation because they will not contribute to the final result. Otherwise, the result will not be optimal.
If two friends do not have a common language then one or both of them need to learn the selected language L.

The upper limit of the number of languages is 500 which is not a large number so we can just iterate through all the languages and calculate how many people need to learn it and we return the language that has the minimal number.

Tip: The problem uses index that starts from 1, which is kind of annoying. When we implement the solution, we can convert it to a 0-index based.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {

public:
    int n;
    vector<vector<bool>> languageSkill;

public:

    void buildLanguageSkill(const vector<vector<int>>& languages) {
        this->languageSkill = vector<vector<bool>>(languages.size(), vector<bool>(this->n, false));

        for (int i = 0; i < languages.size(); ++i) {
            for (auto& k : languages.at(i)) {
                this->languageSkill[i][k-1] = true;
            }
        }
    }

    bool hasCommonLanguage(const int u1, const int u2) {
        for (int i = 0; i < this->n; ++i) {
            if (this->languageSkill[u1][i] == true && this->languageSkill[u2][i] == true) {
                return true;
            }
        }
        return false;
    }

    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        this->n = n;
        this->buildLanguageSkill(languages);
        vector<unordered_set<int>> languageValue = vector<unordered_set<int>>(this->n, unordered_set<int>{});

        for (auto& userPair : friendships) {
            int u1 = userPair[0] - 1;
            int u2 = userPair[1] - 1;
            if (!this->hasCommonLanguage(u1, u2)) {
                for (int i = 0; i < this->n; ++i) {
                    if (!this->languageSkill[u1][i]) {languageValue[i].insert(u1);}
                    if (!this->languageSkill[u2][i]) {languageValue[i].insert(u2);}
                }
            }
        }

        int result = languages.size();
        for (auto& s : languageValue) {
            result = min(result, static_cast<int>(s.size()));
        }
        return result;
    }
};

----- END -----

If you have questions about this post, you could find me on Discord.

Send me a message Subscribe to blog updates

Want some fun stuff?