Community Problem
Find the Town Judge
Difficulty: Easy
Identify the unique person trusted by everyone but trusts nobody, using in-degree minus out-degree.
Find the Town Judge
Identify the unique person trusted by everyone but trusts nobody, using in-degree minus out-degree.
By @chidiweber
April 26, 2026
·
Updated May 20, 2026
606 views
10
4.3 (9)
I had this on a junior phone screen and was struck by how cleanly it teaches "sometimes a graph problem is just a counting problem". The trick is to realize that "trusted by everyone but trusts nobody" is exactly the in-degree minus out-degree equals n - 1 condition. Once you see that, you do not need an adjacency list at all. The catalog covers Graph Representation but skipped this degree-based identifier.
Find the Town Judge
In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge.
If the town judge exists, then:
- The town judge trusts nobody.
- Everybody (except for the town judge) trusts the town judge.
- There is exactly one person that satisfies properties 1 and 2.
You are given an array trust where trust[i] = [a_i, b_i] representing that person a_i trusts person b_i. If a trust relationship does not exist in trust, then it does not exist.
Return the label of the town judge if they exist, otherwise return -1.
Examples
Example 1:
- Input:
n = 2,trust = [[1, 2]] - Output:
2 - Explanation: Person 1 trusts person 2. Person 2 trusts nobody. So 2 is the judge.
Example 2:
- Input:
n = 3,trust = [[1, 3], [2, 3]] - Output:
3 - Explanation: Both 1 and 2 trust 3, and 3 trusts nobody.
Example 3:
- Input:
n = 3,trust = [[1, 3], [2, 3], [3, 1]] - Output:
-1 - Explanation: 3 also trusts 1, so 3 cannot be the judge.
Example 4:
- Input:
n = 1,trust = [] - Output:
1 - Explanation: With one person, they vacuously satisfy both conditions.
Constraints
1 <= n <= 1000.0 <= trust.length <= 10^4.trust[i].length == 2.- All the pairs of
trustare unique. a_i != b_i.1 <= a_i, b_i <= n.
Follow-up
Why is the score-based one-pass solution correct? The judge has in-degree n - 1 and out-degree 0, so score = (n - 1) - 0 = n - 1. No other person can have a higher score because the maximum out-degree-zero person has at most in-degree n - 1 (everyone but themselves), and any out-trust strictly lowers the score. Uniqueness follows from score == n - 1 being achieved by at most one person.
Solution
Hints
Solution Walkthrough
Approach: In-Degree Minus Out-Degree (O(n + |trust|) time, O(n) space)
In graph language, trust defines a directed graph where an edge a -> b means "a trusts b". The judge has:
- in-degree
= n - 1(everyone else trusts them). - out-degree
= 0(they trust nobody).
Define score[p] = inDegree(p) - outDegree(p). The judge has score[p] == n - 1. No other person can: their out-degree is at least 1 OR their in-degree is at most n - 2, so their score is at most n - 2.
Algorithm
- Allocate
score[1..n]initialized to 0. - For each
[a, b]intrust:score[a] -= 1; score[b] += 1. - Scan
p = 1..nand return the firstpwithscore[p] == n - 1. - If none, return
-1.
Why It Works
The judge's score is (n - 1) - 0 = n - 1. We claim only the judge can achieve n - 1. Suppose another person q also has score[q] == n - 1. Then inDegree(q) - outDegree(q) == n - 1. Since both are in [0, n], the only solution is inDegree(q) = n - 1, outDegree(q) = 0. Both conditions match the judge's exact criteria, so q is also a judge. The problem guarantees at most one judge exists, so q must equal the unique judge.
The algorithm correctly returns -1 if no such person exists, since the loop never finds a score == n - 1.
Complexity
Sample
n=4, trust=[[1,3],[1,4],[2,3],[2,4],[4,3]]
score[1] -= 2 -> -2 (person 1 trusts 2 others)
score[2] -= 2 -> -2
score[3] += 3 -> +3 (3 trusts no one)
score[4] += 1, score[4] -= 1 -> 0 (4 is trusted twice but trusts once)
Looking for score == n - 1 = 3 -> person 3 wins.Metric Value
Time O(n + |trust|)
Space O(n) for the score arrayPitfalls
- Building an adjacency list. Tempting but wasteful here. The score is all you need.
- Off-by-one on
n - 1. The judge's score isn - 1, NOTn. Trusting nobody means the judge's outgoing contribution is0, and EVERYONE ELSE (n - 1people) trusts them. - Forgetting the singleton case. When
n = 1, the loop body findsscore[1] == 0 == n - 1. The single person is vacuously a judge.
Solution Code