Mutual friends
Put neighbours in sets, then count the people who appear in both. About 9 minutes.
"You have 1 mutual friend"
Every social app shows this line when you open someone's profile. How does it work? Take your friend list and their friend list, and count the names that appear on both.
To make "is this person on their list?" instant, store each person's friends in a set instead of a list, the same trick you used in Hashing.
adj = [set() for _ in range(n)]
for u, v in edges:
adj[u].add(v)
adj[v].add(u)
return len(adj[a] & adj[b])- adj[0]
- {1, 2}
- mutual
- 0
Start with a = 0. Its friends are 1 and 2.
Walk one list, check the other
Go through the first person's friends one by one. For each friend, ask the second person's set "do you have this person too?" and count the yeses. You only walk one list, so the work is about the size of one friend list, not the whole network.
Try it below with person 0 and person 3.
Friends are 0–1, 0–2, 1–2. How many mutual friends do 0 and 1 have?
- A1 (node 2)
- B2
- C0
Show the answer
1 (node 2). 0's friends are {1, 2}, 1's friends are {0, 2}. Only 2 is on both lists.
Mutual friends
A social app has n users numbered 0 to n - 1, and edges lists friendships: [u, v] means u and v are friends (both ways). For two different users a and b, return how many users are friends with both of them.
n = 5, edges = [[0, 1], [0, 2], [1, 2], [2, 3], [3, 4]], a = 0, b = 3 → 1
1 ≤ n ≤ 100,000 · 0 ≤ edges.length ≤ 100,000 · 0 ≤ u, v < n · no edge joins a node to itself and no edge appears twice · 0 ≤ a, b < n · a ≠ b