Minimum Number of People to Teach

MEDIUM

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 users 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 3, yielding two users to teach.

Constraints:

2 <= n <= 500
languages.length == m
1 <= m <= 500
1 <= languages[i].length <= n
1 <= languages[i][j] <= n
1 <= u_i < v_i <= languages.length
1 <= friendships.length <= 500
All tuples (u_i,v_i) are unique
languages[i] contains only unique values

Approaches

Checkout 2 different approaches to solve Minimum Number of People to Teach. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Check for Each Language

This approach iterates through every possible language from 1 to n that we could teach. For each candidate language, it determines the number of users that would need to be taught this language to satisfy all friendship communication requirements. The minimum count across all languages is the answer.

Algorithm

Initialize minTeachings to a very large value (e.g., the total number of users).
For each language l from 1 to n:
- Create an empty set usersToTeachForL to store unique users who need to be taught language l.
- For each friendship [u, v]:
  - Check if users u and v share a common language. This check itself can be done by iterating through the languages of one user and checking for existence in the other's language list.
  - If they do not share a common language:
    - Check if user u already knows language l. If not, add u to the usersToTeachForL set.
    - Check if user v already knows language l. If not, add v to the usersToTeachForL set.
- After checking all friendships, the size of the usersToTeachForL set is the number of teachings required for language l.
- Update minTeachings = min(minTeachings, usersToTeachForL.size()).
Return minTeachings.

The algorithm iterates through each language l from 1 to n. For each l, we calculate the number of people to teach. We initialize a set, usersToTeach, to keep track of them to avoid duplicates. We then iterate through every friendship [u, v]. For each friendship, we first check if users u and v can already communicate. This is done by checking if their sets of known languages have a non-empty intersection. If they cannot communicate, they form a 'disconnected pair'. For this pair to communicate using language l, both must know it. We check if user u already knows language l. If not, we add u to our usersToTeach set for language l. We do the same for user v. After checking all friendships, the size of the usersToTeach set gives the total number of teachings required for language l. We keep track of the minimum size found so far across all languages. Finally, after checking all n languages, we return the overall minimum.

To make language lookups efficient, we first convert the input languages array into an array of HashSets.

class Solution {
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int m = languages.length;
        // Convert languages to Sets for easier lookup
        Set<Integer>[] langSets = new HashSet[m + 1];
        for (int i = 1; i <= m; i++) {
            langSets[i] = new HashSet<>();
            for (int lang : languages[i - 1]) {
                langSets[i].add(lang);
            }
        }

        int minTeachings = m; // Maximum possible teachings is m

        for (int l = 1; l <= n; l++) {
            Set<Integer> usersToTeach = new HashSet<>();
            for (int[] friendship : friendships) {
                int u = friendship[0];
                int v = friendship[1];

                if (!canCommunicate(langSets, u, v)) {
                    if (!langSets[u].contains(l)) {
                        usersToTeach.add(u);
                    }
                    if (!langSets[v].contains(l)) {
                        usersToTeach.add(v);
                    }
                }
            }
            minTeachings = Math.min(minTeachings, usersToTeach.size());
        }
        return minTeachings;
    }

    private boolean canCommunicate(Set<Integer>[] langSets, int u, int v) {
        Set<Integer> langU = langSets[u];
        Set<Integer> langV = langSets[v];
        // Iterate over the smaller set for efficiency
        if (langU.size() > langV.size()) {
            Set<Integer> temp = langU;
            langU = langV;
            langV = temp;
        }
        for (int lang : langU) {
            if (langV.contains(lang)) {
                return true;
            }
        }
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n * F * L), where `n` is the number of languages, `F` is the number of friendships, and `L` is the maximum number of languages a user knows. We iterate through `n` languages. For each, we iterate through `F` friendships. The `canCommunicate` check takes `O(L)` time with pre-processed sets.Space Complexity: O(m * L + m), where `m` is the number of users and `L` is the maximum number of languages a user knows. `O(m*L)` space is used to store the language sets for each user, and the `usersToTeach` set can hold at most `m` users.

Pros and Cons

Pros:

The logic is straightforward and directly models the problem of trying each possible language.

Cons:

This approach is inefficient because it repeatedly calculates which friendships are 'disconnected' for each of the n languages. This leads to a higher time complexity.

Code Solutions

Checking out 3 solutions in different languages for Minimum Number of People to Teach. Click on different languages to view the code.

class Solution {
public
  int minimumTeachings(int n, int[][] languages, int[][] friendships) {
    Set<Integer> s = new HashSet<>();
    for (var e : friendships) {
      int u = e[0], v = e[1];
      if (!check(u, v, languages)) {
        s.add(u);
        s.add(v);
      }
    }
    if (s.isEmpty()) {
      return 0;
    }
    int[] cnt = new int[n + 1];
    for (int u : s) {
      for (int l : languages[u - 1]) {
        ++cnt[l];
      }
    }
    int mx = 0;
    for (int v : cnt) {
      mx = Math.max(mx, v);
    }
    return s.size() - mx;
  }
private
  boolean check(int u, int v, int[][] languages) {
    for (int x : languages[u - 1]) {
      for (int y : languages[v - 1]) {
        if (x == y) {
          return true;
        }
      }
    }
    return false;
  }
}

Video Solution

Watch the video walkthrough for Minimum Number of People to Teach

Patterns:

Greedy

Data Structures:

ArrayHash Table

Companies:

Duolingo |