Minimum Number of People to Teach LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool checkinvalid(int a, int b,
4
                    vector<vector<int>> &languages) { // helper func., checks if a
5
                                                      // and b can communicate or not
6
    a--;
7
    b--;
8
    for (int i = 0; i < languages[a].size(); i++) {
9
      if (find(languages[b].begin(), languages[b].end(), languages[a][i]) != languages[b].end())
10
        return false;
11
    }
12
    return true;
13
  }
14

15
  int minimumTeachings(int n, vector<vector<int>> &languages, vector<vector<int>> &friendships) {
16
    int m = languages.size();
17
    vector<vector<int>> g(m + 1, vector<int>(0)); // graph to store adjacency list with people as
18
                                                  // nodes & friendships as edges
19
    // create graph
20
    for (int i = 0; i < friendships.size(); i++) {
21
      g[friendships[i][0]].push_back(friendships[i][1]);
22
      g[friendships[i][1]].push_back(friendships[i][0]);
23
    }
24

25
    vector<int> voters(m + 1, 0); // to store people who cant communicate with atleast a friend
26
    int voterscount = 0;
27
    for (int i = 1; i < m + 1; i++) {
28
      for (int j = 0; j < g[i].size(); j++) {
29
        if (checkinvalid(i, g[i][j], languages)) { // ith can vote
30
          voters[i] = 1;
31
          voterscount++;
32
          break;
33
        }
34
      }
35
    }
36
    unordered_map<int, int> mappy; // language -> votes
37
    int maxvotes = 0;
38

39
    for (int i = 1; i < m + 1; i++) {
40
      if (voters[i] == 1) {
41
        for (int j : languages[i - 1]) {
42
          mappy[j]++;
43

44
          if (maxvotes < mappy[j]) {
45
            maxvotes = mappy[j];
46
          }
47
        }
48
      }
49
    }
50
    return voterscount - maxvotes; // # who need to be taught the language
51
  }
52
};