We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Number of People to Teach

Number: 1834

Difficulty: Medium

Paid? No

Companies: Duolingo

Problem Description

Given a social network of users with known languages and friendships, two users can communicate if they share at least one common language. We are allowed to choose exactly one language and teach it to certain users. The goal is to determine the minimum number of users that need to be taught that language so that every friendship pair has at least one common language.

Key Insights

  • Only friendship pairs that currently do not share a common language are problematic.
  • Collect the unique set of users from the problematic friendship pairs; these are candidates for being taught.
  • For each candidate language (from 1 to n), count how many users in the candidate set do not already know that language.
  • The optimal language to teach is the one that minimizes the number of additional users required.

Space and Time Complexity

Time Complexity: O(f * L + n * k)

  • f is the number of friendships,
  • L is the average number of languages per user,
  • n is the total number of languages, and
  • k is the number of users who are part of at least one problematic friendship. Space Complexity: O(m + k)
  • m for storing language sets for m users and k for the candidate set.

Solution

  1. Convert the list of languages for each user into a set for fast lookup.
  2. Iterate over each friendship pair; if the two friends have no common language (i.e. their language sets' intersection is empty), add both users to a candidate set.
  3. For each possible language from 1 to n, count how many users in the candidate set do not know that language.
  4. Return the minimum count across all candidate languages. This language is the one that minimizes the number of additional teachings required.
  5. Teaching users who are already knowledgeable about the chosen language is unnecessary.

Code Solutions

# Python solution for Minimum Number of People to Teach

def minimum_teachers(n, languages, friendships):
    # Convert each user's languages list to a set for fast lookup.
    user_languages = [set(lang_list) for lang_list in languages]
    
    # Set to maintain users (0-indexed) involved in problematic friendships
    need_teach = set()
    
    # Process each friendship: if there is no common language, mark both users.
    for u, v in friendships:
        # Adjust for 0-based index
        u_idx, v_idx = u - 1, v - 1
        # Check if they don't share any language
        if user_languages[u_idx].isdisjoint(user_languages[v_idx]):
            need_teach.add(u_idx)
            need_teach.add(v_idx)
    
    # If no users need to be taught, then no action is required.
    if not need_teach:
        return 0
    
    # For each language candidate, count the number of users in need_teach that do not know it.
    min_teach_required = float('inf')
    for language in range(1, n + 1):
        # Count how many users from the need_teach set do not have this language
        teach_count = 0
        for user in need_teach:
            if language not in user_languages[user]:
                teach_count += 1
        min_teach_required = min(min_teach_required, teach_count)
    
    return min_teach_required

# Example usage:
n = 2
languages = [[1], [2], [1,2]]
friendships = [[1,2], [1,3], [2,3]]
print(minimum_teachers(n, languages, friendships))  # Output: 1
← Back to All Questions