675. Village Judge
In a village of n residents labelled 1 to n, a rumour says there is a secret judge. If the judge exists, two things hold: the judge trusts nobody, and every other resident trusts the judge. Each entry trust[i] = [a, b] says that resident a trusts resident b. No pair appears twice and nobody trusts themself.
Return the label of the judge, or -1 if the village has no judge. Since all other residents must trust the judge, there can never be two judges. A village of a single person with an empty list has that person as its judge. Aim for O(n + m) time and O(n) space, where m is the number of trust pairs.
Example 1
- Input:
- n = 4, trust = [[1,4],[2,4],[3,4],[1,2]]
- Output:
- 4
- Explanation:
Resident 4 trusts nobody and is trusted by the other three, so 4 is the judge.
Example 2
- Input:
- n = 3, trust = [[1,2],[2,3],[3,1]]
- Output:
- -1
- Explanation:
Everyone trusts someone, so nobody can be the judge.
Example 3
- Input:
- n = 1, trust = []
- Output:
- 1
- Explanation:
A single resident trusts nobody and is trusted by all zero others, so resident 1 is the judge.
Constraints
1 ≤ n ≤ 1000
0 ≤ trust.length ≤ 10000
1 ≤ a, b ≤ n, a ≠ b, and all pairs are distinct
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n)