Minimum Number of People to Teach LeetCode Solution

Difficulty Level Medium
DuolingoViews 153

Problem Statement

Minimum Number of People to Teach LeetCode Solution- 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 users u​​​​​​​​​​​i​​​​​ and vi.

You can choose one language and teach it to some users so that all your 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.

 

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.

Explanation

This sentence is important! “You can choose one language and teach it to some users so that all friends can communicate with each other.”
This should be understood as you can choose only one language to teach to all the people, rather than teaching different languages to different people.

  • The key idea is to try each language one by one since we are only allowed to use one language
  • Then iterate over each friendship.
    • If the two friends can already communicate via a common language, ignore them and move on to the next friendship
    • Otherwise, teach them the language (assuming they don’t know it already)
    • Find the minimum number of friends to teach any language

Code

C++ Code for Minimum Number of People to Teach

class Solution {
public:

  // Memoize results since the same query is asked repeatedly
  vector<vector<int>> mem;  	
  
  // Check to see if u and v already speak a common language
    bool check(vector<vector<int>>& a, int u, int v) {
        if(mem[u][v] != 0) return mem[u][v] == 1;
        for(int i=0; i<a[v].size(); i++) {
            if(find(a[u].begin(), a[u].end(), a[v][i]) != a[u].end()) {
                mem[v][u] = mem[u][v] = 1;
                return true;
            }
        }
        mem[u][v] = mem[v][u] = -1;
        return false;
    }
  
    int minimumTeachings(int n, vector<vector<int>>& languages, vector<vector<int>>& friendships) {
        int m = languages.size(), ret = m, i;
        mem.assign(m + 1, vector<int>(m + 1, 0));
    
        for(i=0; i<m; i++)
            sort(languages[i].begin(), languages[i].end()); 		// May not be necessary, just a precaution
      
        for(int lang=1; lang<=n; lang++) {
            int count = 0;
            vector<bool> teach(m, false);
            for(i=0; i<friendships.size(); i++) {
                int u = friendships[i][0] - 1;
                int v = friendships[i][1] - 1;
                if(check(languages, u, v)) 
                    continue;
                if(find(languages[u].begin(), languages[u].end(), lang) == languages[u].end()) {
                    if(!teach[u])
                        count++;
                    teach[u] = true;
                }
                if(find(languages[v].begin(), languages[v].end(), lang) == languages[v].end()) {
                    if(!teach[v])
                        count++;
                    teach[v] = true;
                }
            }
            ret = min(ret, count);
        }
        return ret;
    }
};

Java Code for Minimum Number of People to Teach

class Solution {
  public int minimumTeachings(int n, int[][] languages, int[][] friendships) {

    // record the languages known to every user
    Map<Integer,Set<Integer>> ul = new HashMap<>();
    for(int i=0; i<languages.length; i++) {
      Set<Integer> lang = new HashSet<>();
      ul.put(i+1, lang);
      for(int l : languages[i]) {
        lang.add(l);
      }
    }

    // if two users are friends and they can't speak to each other due to language issue, record it
    Map<Integer,Set<Integer>> uf = new HashMap<>();
    for(int i=0; i<friendships.length; i++) {
      int[] frnd = friendships[i];
      boolean canSpk = false;
      for(int l : ul.get(frnd[0])) {
        if(ul.get(frnd[1]).contains(l)) {
          canSpk = true;
          break;
        }
      }
      if(canSpk) continue;
      
      uf.putIfAbsent(frnd[0],new HashSet<>());
      uf.putIfAbsent(frnd[1],new HashSet<>());
      uf.get(frnd[0]).add(frnd[1]);
      uf.get(frnd[1]).add(frnd[0]);
    }
    
    int ans = Integer.MAX_VALUE;
    // for every language, see how many users need to learn it
    for(int i=1; i<=n; i++) {
      int tot = 0;
    // if we have to teach language i, then how many users need to learn this?
      for(int key : uf.keySet()) {
        if(!ul.get(key).contains(i)) tot++;
      }
      // if this language needs to be learned by less number of people, then this is the answer, else don't override the ans
      ans = Math.min(ans, tot);
    }
    
    return ans;
  }
}

Python Code for Minimum Number of People to Teach

class Solution:
     def minimumTeachings(self, n: int, languages: List[List[int]], friendships: List[List[int]]) -> int:
            languages = [set(l) for l in languages]

            dontspeak = set()
            for u, v in friendships:
                u = u-1
                v = v-1
                if languages[u] & languages[v]: continue
                dontspeak.add(u)
                dontspeak.add(v)

            langcount = Counter()
            for f in dontspeak:
                for l in languages[f]:
                    langcount[l] += 1

            return 0 if not dontspeak else len(dontspeak) - max(list(langcount.values()))

Complexity Analysis for Minimum Number of People to Teach LeetCode Solution

Time Complexity

O(M*N)

Space Complexity

O(N)

Reference: https://en.wikipedia.org/wiki/Greedy_algorithm

Translate »