Loading page…
Practice problem · medium
In a chat app, you can add someone as a contact, and they do not have to add you back. The app has n people, numbered 0 to n - 1, and a list of contacts: [a, b] means person a added person b.
Two people are mutual when each added the other. You work on the "You may know" feature, which starts from mutual pairs, so you need to count them.
Write mutual_pairs(n, contacts).
n is the number of people.contacts[i] = [a, b] means person a added person b. Each pair appears at most once, and nobody adds themselves.{a, b} where a added b and b added a. Count each pair of people once.Input: n = 5, contacts = [[0, 1], [1, 0], [1, 2], [2, 3], [3, 2], [0, 4]]
Output: 2| Contact | Does the reverse exist? | Counted? |
|---|---|---|
[0, 1] |
[1, 0] is there |
yes, from the smaller end |
[1, 0] |
[0, 1] is there |
no: the pair was counted from 0 |
[1, 2] |
[2, 1] is missing |
no |
[2, 3] |
[3, 2] is there |
yes |
[3, 2] |
[2, 3] is there |
no: counted from 2 |
[0, 4] |
[4, 0] is missing |
no |
Two pairs are mutual: 0 and 1, and 2 and 3.
Input: n = 3, contacts = [[0, 1], [1, 2]]
Output: 0Nobody added the person who added them, so no pair is mutual.
Input: n = 2, contacts = [[0, 1], [1, 0]]
Output: 1Person 0 added 1, and 1 added 0. That is one pair, not two.
1 ≤ n ≤ 10^50 ≤ length of contacts ≤ 2 · 10^50 ≤ a, b < n, a ≠ b, and each pair appears at most onceThere can be 200,000 contacts. For each contact, scanning the whole list to find its reverse takes 200,000 times 200,000 steps, about forty billion. That is far too slow.
Asking "did b add a?" must cost one step. A set of pairs, or a set of neighbours for each person, answers it that fast.
mutual_pairs · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.