Find the Town Judge
Easy · Graphs · Array · Hash Table · Graph
Problem
A town has n people labelled 1 to n, and one of them may secretly be the town judge. If the judge exists:
- The judge trusts nobody.
- Everybody else trusts the judge.
- Exactly one person satisfies both rules.
trust[i] = [a, b] means person a trusts person b; trust goes one way only. Return the judge's label if the judge can be identified, or -1 otherwise.
Think of the people as nodes and each trust pair as a directed edge a → b. The judge is the one node with in-degree n - 1 and out-degree 0.
Examples
Input: n = 4, trust = [[1,3],[2,3],[4,3],[4,1]] Output: 3
Persons 1, 2 and 4 all trust 3, and 3 trusts nobody. Person 4 also trusting 1 does not matter.
Input: n = 3, trust = [[1,2],[2,3],[3,1]] Output: -1
Everyone trusts someone, so nobody can be the judge.
Input: n = 1, trust = [] Output: 1
The only person trusts nobody, and there is nobody else who needs to trust them.
Constraints
- 1 <= n <= 1000
- 0 <= len(trust) <= 10^4
- trust[i] == [a, b] with a != b and 1 <= a, b <= n
- all pairs in trust are different
Approaches
- Check every person against every pair — time O(n · t), space O(1)
Follow-up
Why can at most one person ever have score n - 1? (If two did, each would have to trust the other, and the judge trusts nobody.) The same degree trick finds a "celebrity" when the trust relation comes as a yes/no question you can ask about any pair: one elimination pass, then one check.
Related problems
Start free on Cariara · Coding problems · System design studio
