Loading page…
Practice problem · easy
A small town has an app where residents follow each other's accounts. There are n residents, numbered 0 to n - 1, and a list of follows: [a, b] means resident a follows resident b.
The town has at most one judge. The judge is followed by every other resident, and follows nobody. You write the check that finds the judge.
Write find_judge(n, follows).
n is the number of residents.follows[i] = [a, b] means resident a follows resident b. Each pair appears at most once, and nobody follows themselves.n - 1 others follow, and that follows nobody. Return -1 when there is no such resident.Input: n = 4, follows = [[0, 3], [1, 3], [2, 3], [0, 1]]
Output: 3| Resident | Followed by | Follows | Judge? |
|---|---|---|---|
| 0 | none | 3, 1 | no |
| 1 | 0 | 3 | no |
| 2 | none | 3 | no |
| 3 | 0, 1, 2 | nobody | yes |
Resident 3 is followed by all three others and follows nobody.
Input: n = 3, follows = [[0, 2], [1, 2], [2, 0]]
Output: -1Resident 2 is followed by both others, but follows resident 0, so 2 is not the judge. Nobody else is followed by everyone.
Input: n = 1, follows = []
Output: 0One resident: all zero other residents follow them, and they follow nobody. They are the judge.
1 ≤ n ≤ 10^50 ≤ length of follows ≤ 10^50 ≤ a, b < n, a ≠ b, and each pair appears at most onceThere can be 100,000 residents. Checking each resident against every other resident takes n times n steps, which is ten billion for 100,000. That is too slow.
The judge is described by two counts: how many follow them and how many they follow. Counting both for everyone takes one pass over the pairs.
find_judge · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.