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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Number of People to Teach

Difficulty: Medium

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

Key Insights

  • Users can only communicate if they share at least one common language.
  • Friendships are not transitive; communication must occur directly between friends.
  • The problem can be viewed as a graph where users are nodes and friendships are edges.
  • The goal is to ensure communication across all connected components of the graph by teaching a common language to the minimum number of users.

Space and Time Complexity

Time Complexity: O(m + f * k), where m is the number of users, f is the number of friendships, and k is the average number of languages known by users.
Space Complexity: O(m + f), where m is the number of users and f is the number of friendships.

Solution

The problem can be solved using a graph-based approach. First, we construct an adjacency list to represent the friendships between users. Next, we identify connected components in the graph. For each connected component, we determine the languages known by the users in that component. The minimum number of users that need to be taught a new language to ensure communication within the component can be found by counting how many users do not know the most commonly spoken language in that component. Finally, we sum the minimums across all components to get the final answer.

Code Solutions

from collections import defaultdict, Counter

def minimumTeachings(n, languages, friendships):
    # Create a graph from friendships
    graph = defaultdict(list)
    for u, v in friendships:
        graph[u - 1].append(v - 1)
        graph[v - 1].append(u - 1)

    visited = [False] * len(languages)
    components = []

    # Function to perform DFS and find connected components
    def dfs(node, component):
        stack = [node]
        while stack:
            curr = stack.pop()
            if not visited[curr]:
                visited[curr] = True
                component.append(curr)
                for neighbor in graph[curr]:
                    if not visited[neighbor]:
                        stack.append(neighbor)

    # Find all connected components
    for i in range(len(languages)):
        if not visited[i]:
            component = []
            dfs(i, component)
            components.append(component)

    total_users_to_teach = 0

    # For each component, calculate the minimum users to teach
    for component in components:
        lang_count = Counter()
        for user in component:
            for lang in languages[user]:
                lang_count[lang] += 1

        # Find the maximum frequency of spoken languages
        max_known = max(lang_count.values(), default=0)
        # Users to teach is the size of component minus max known
        total_users_to_teach += len(component) - max_known

    return total_users_to_teach
← Back to All Questions