Leetcode 1733 - Minimum Number of People to Teach

Subscribe Send me a message home page


Link to Problem

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:

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:

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 -----

Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png


Comments