Find the Town Judge
Easy· Degree Counting
Problem
A town has n people labelled 1 to n, and trust[i] = [a, b] means a trusts b. The judge, if one exists, trusts nobody and is trusted by everyone else. Return the judge's label, or -1 if no such person exists.
Examples
Input: n = 3, trust = [[1,3],[2,3]]
Output: 3
Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Person 3 trusts person 1, so 3 cannot be the judge.
Constraints
- • 1 <= n <= 1000
- • 0 <= trust.length <= 10^4
- • All trust pairs are unique and a != b
Hints & approach
Hint 1
View trust as directed edges and think about in-degree and out-degree.
Hint 2
The judge has in-degree n - 1 and out-degree 0.
Hint 3
A single score of in-degree minus out-degree is enough.
Approachtry the hints first
Keep one score per person. For each pair [a, b], decrement score[a] and increment score[b]. The judge is the unique person whose score equals n - 1, since that is only reachable with n - 1 incoming edges and no outgoing ones. Return that person, or -1 if none exists.
Time O(n + t) · Space O(n)