Find the Town Judge
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
