{x}
blog image

Minimum Number of People to Teach

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

Solution Explanation: Minimum Number of People to Teach

This problem asks to find the minimum number of people to teach a new language to, so that all pairs of friends can communicate (meaning they share at least one common language).

Approach:

  1. Identify Non-Communicating Friends: The solution first iterates through the friendships array. For each friendship pair, it checks if the two users can already communicate (i.e., share a common language). If they cannot, both users are added to a set s which keeps track of the people needing to be taught.

  2. Language Count: The solution then iterates through the set s. For each person in s, it counts how many times each language appears across all their known languages. This is done using a counter (e.g., Counter in Python, a Map in Java, vector in C++, or a slice in Go). This counter keeps track of the languages that are already known by people that need teaching.

  3. Minimum Teachings: Finally, the solution determines the maximum count of any single language from the counter (cnt). This represents the maximum number of people in s who already know a certain language. Subtracting this maximum count from the total number of people in s gives the minimum number of additional people who need to be taught a language to ensure all friends can communicate.

Time Complexity Analysis:

  • Step 1: Checking if two users can communicate takes O(k1 * k2) time in the worst case, where k1 and k2 are the number of languages known by the two users. Iterating through all friendships adds a factor of len(friendships). Thus this step is O(len(friendships) * max(k1, k2)^2). In the worst-case scenario, max(k1, k2) is proportional to n which is the maximum number of languages.
  • Step 2: This step iterates through the set s (which has at most 2 * len(friendships) elements in the worst case) and each person's languages. This has a time complexity of O(len(s) * n).
  • Step 3: Finding the maximum count in cnt is done in O(n) time.

Therefore, the overall time complexity is dominated by the first step resulting in approximately O(len(friendships) * n^2). Note that in practice, the number of languages a person knows is usually much smaller than n, so the practical performance can be significantly better than the worst-case complexity.

Space Complexity: The space complexity is determined by the size of the set s and the counter cnt. In the worst case, s can contain up to 2 * len(friendships) elements, and cnt has a size of n + 1. Therefore, the space complexity is approximately O(len(friendships) + n).