Minimum Number of People to Teach

Minimum Number of People to Teach - Problem

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
friendships[i] = [u_i, v_i] denotes a friendship between 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.

Input & Output

Example 1 — Basic Communication Problem

$ Input: n = 2, languages = [[1],[2],[1,2]], friendships = [[1,2],[1,3],[2,3]]

› Output: 1

💡 Note: User 1 speaks [1], User 2 speaks [2] - they cannot communicate. User 3 speaks [1,2] and can talk to both. Teaching language 1 to User 2 or language 2 to User 1 solves all problems with 1 person taught.

Example 2 — No Teaching Needed

$ Input: n = 3, languages = [[2],[1,3],[1,2]], friendships = [[1,2],[1,3],[2,3]]

› Output: 0

💡 Note: User 1:[2] and User 2:[1,3] have no common language, but User 1:[2] and User 3:[1,2] share language 2, and User 2:[1,3] and User 3:[1,2] share language 1. All friendships can communicate, so 0 users need teaching.

Example 3 — Multiple Isolated Groups

$ Input: n = 3, languages = [[1],[2],[3]], friendships = [[1,2],[2,3]]

› Output: 1

💡 Note: User 1:[1] and User 2:[2] cannot communicate, User 2:[2] and User 3:[3] cannot communicate. Teaching any language to User 2 allows all three to communicate through User 2 as intermediary.

Constraints

2 ≤ n ≤ 500
languages.length == m
1 ≤ m ≤ 500
1 ≤ languages[i].length ≤ n
1 ≤ languages[i][j] ≤ n
1 ≤ friendships.length ≤ 500
friendships[i].length == 2

Visualization

Tap to expand

Asked in

f Facebook 25 G Google 18 M Microsoft 12

The key insight is to identify friendship pairs that cannot currently communicate (no shared languages) and then find the language that requires teaching the minimum number of users to enable all communication. The greedy approach optimizes by focusing only on users involved in problematic friendships rather than considering all possible languages. Time: O(n × F × L), Space: O(F)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Optimize Language Selection	O(F × L + n × U)	O(F + U)	Focus only on users in problematic friendships and greedily select the most beneficial language
Brute Force - Try All Languages	O(n × F × L)	O(F)	For each language, count how many users need to learn it to enable all communication

Greedy - Optimize Language Selection — Algorithm Steps

Find problematic friendships
Collect all users involved in these friendships
For each language, prioritize based on how many involved users already know it
Select language requiring minimum new learners

Visualization

Tap to expand

Step-by-Step Walkthrough

Identify Issues

Find users involved in communication problems

Smart Selection

Prioritize languages known by involved users

Optimal Choice

Choose language requiring minimum teaching

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int n, int** languages, int* langSizes, int languagesSize, int** friendships, int friendshipsSize) {
    // Simplified implementation for C
    int problematic[1000][2];
    int probCount = 0;
    
    for (int i = 0; i < friendshipsSize; i++) {
        int u = friendships[i][0] - 1;
        int v = friendships[i][1] - 1;
        
        int hasCommon = 0;
        for (int j = 0; j < langSizes[u] && !hasCommon; j++) {
            for (int k = 0; k < langSizes[v]; k++) {
                if (languages[u][j] == languages[v][k]) {
                    hasCommon = 1;
                    break;
                }
            }
        }
        
        if (!hasCommon) {
            problematic[probCount][0] = u;
            problematic[probCount][1] = v;
            probCount++;
        }
    }
    
    if (probCount == 0) return 0;
    
    int minTeach = INT_MAX;
    
    for (int lang = 1; lang <= n; lang++) {
        int usersToTeach[500] = {0};
        int teachCount = 0;
        
        for (int i = 0; i < probCount; i++) {
            int u = problematic[i][0];
            int v = problematic[i][1];
            
            int uKnows = 0, vKnows = 0;
            
            for (int j = 0; j < langSizes[u]; j++) {
                if (languages[u][j] == lang) {
                    uKnows = 1;
                    break;
                }
            }
            
            for (int j = 0; j < langSizes[v]; j++) {
                if (languages[v][j] == lang) {
                    vKnows = 1;
                    break;
                }
            }
            
            if (!uKnows && !vKnows) {
                if (!usersToTeach[u]) {
                    usersToTeach[u] = 1;
                    teachCount++;
                }
            } else if (!uKnows) {
                if (!usersToTeach[u]) {
                    usersToTeach[u] = 1;
                    teachCount++;
                }
            } else if (!vKnows) {
                if (!usersToTeach[v]) {
                    usersToTeach[v] = 1;
                    teachCount++;
                }
            }
        }
        
        if (teachCount < minTeach) {
            minTeach = teachCount;
        }
    }
    
    return minTeach;
}

int main() {
    printf("1\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(F × L + n × U)

F friendships × L languages to find problems + n languages × U users in problematic pairs

✓ Linear Growth

Space Complexity

O(F + U)

Store problematic friendships and set of users involved in communication issues

✓ Linear Space

12.5K Views

Medium Frequency

~25 min Avg. Time

420 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Optimize Language Selection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler