Skip to main content
medium

Minimum Number of People to Teach

Pen-pal club with n languages and some people, all numbered from 1. Person i + 1 speaks the languages listed in languages[i]: at least one id, no repeats, any order. Each pair [a, b] in friendships (a < b, no pair listed twice) is two people who want to write to each other, which only works in a language both of them speak. The club can fund one crash course in a single language of your choice, open to as many people as you like, and they keep the languages they already speak. Return the fewest people who must take it so that every friendship can write. Limits: 2 <= n <= 500 2 <= m <= 500, where m = languages.length 1 <= friendships.length <= 500 Think about: a person can sit in several friendships that cannot write yet, but only takes the course once. Example n = 3 languages = [[1,2],[2],[3],[2]] friendships = [[1,3],[2,3],[3,4],[1,2],[2,4]] answer = 1 Pairs (1,3), (2,3) and (3,4) cannot write yet, and person 3 is in all of them. Pairs (1,2) and (2,4) already share language 2, so one seat for person 3 in language 2 fixes every friendship.

You're running a pen-pal club where two friends can write to each other only in a language they both speak. The club will fund one crash course in a language of your choosing, and you want the fewest seats that get every friendship writing. Interviewers love it because it rewards counting the right people, and the classic trap is tallying a member once for every stuck friendship they're in. You get up to 500 members, 500 languages and 500 friendships.

Examples

You write

minimum_teachings(n: int, languages: List[List[int]], friendships: List[List[int]])

  1. Example 1

    Input
    n = 3, languages = [[1,2],[2],[3],[2]], friendships = [[1,3],[2,3],[3,4],[1,2],[2,4]]
    returns
    1
  2. Example 2

    Input
    n = 4, languages = [[1,2],[2,3],[3,4],[4,1],[1,3]], friendships = [[1,2],[2,3],[3,4],[4,5],[1,5],[3,5]]
    returns
    0

The pattern behind it

Arrays & Hashing

I reach for it when

  • You catch yourself scanning the array again for every element.
  • The problem asks about duplicates, pairs, counts or groups.

Say this before you type. Say what the key is and what the value remembers, before you write the loop.

All 127 Arrays & Hashing problems

Greedy

I reach for it when

  • A locally best choice looks safe.
  • You sort first, then sweep once.

Say this before you type. Say the greedy choice, then say why swapping it for another choice cannot do better.

All 17 Greedy problems

Meet Coco

Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.

1Minimum Number of People to Teachmedium