Find the Town Judge
Identify the one node with in-degree n-1 and out-degree 0, using a single trust-score array
Problem Statement
In a town of n people labelled 1 to n, there is a rumour that one of them is secretly the town judge. The judge satisfies three properties:
- The judge trusts nobody.
- Everybody else trusts the judge.
- Exactly one person satisfies both.
You are given trust, where trust[i] = [a, b] means person a trusts person b. Return the judge's label, or -1 if there is no judge.
Input: n = 2, trust = [[1, 2]]
Output: 2
Input: n = 3, trust = [[1, 3], [2, 3]]
Output: 3
Input: n = 3, trust = [[1, 3], [2, 3], [3, 1]]
Output: -1 (3 trusts someone, so 3 cannot be the judge)Intuition
This is a graph problem in disguise. Each person is a node, and [a, b] is a directed edge from a to b.
Restating the rules in graph language
- "The judge trusts nobody" → out-degree = 0
- "Everybody else trusts the judge" → in-degree = n - 1
So you are looking for the unique node with in-degree n - 1 and out-degree 0. No traversal, no BFS, no DFS — just counting edges.
You could keep two arrays, in_degree and out_degree. But there is a neater encoding.
The key insight — one score instead of two
Give every person a single score:
- Trusting someone: -1 to the truster (they can no longer be the judge)
- Being trusted: +1 to the trustee
The judge is the only person who can reach a score of exactly n - 1: they gain +1 from each of the other n - 1 people and lose nothing.
Nobody else can reach it. A non-judge trusts at least one person (the judge), so they carry a -1, capping their score at n - 2.
Watch it run
Approach
Create a score array of size n + 1
Index 0 is unused so the labels 1 … n map directly to indices — no - 1 arithmetic anywhere.
For each [a, b]
score[a] -= 1 and score[b] += 1.
Scan for a score of n - 1
Return that person's label.
Solution
def find_judge(n: int, trust: list[list[int]]) -> int:
"""Return the town judge's label, or -1 if there is none."""
# Index 0 is unused so people map straight onto indices 1..n.
score = [0] * (n + 1)
for truster, trustee in trust:
score[truster] -= 1 # trusting someone disqualifies you
score[trustee] += 1 # being trusted moves you toward n - 1
for person in range(1, n + 1):
if score[person] == n - 1:
return person
return -1Why a score of n - 1 is provably unique
Suppose two people both scored n - 1. Each would need +1 from all n - 1 others, including from each other. But receiving trust from the other means that other person trusts someone — costing them a -1 and capping them at n - 2. Contradiction.
So the first match found is the only match, and returning immediately is safe.
Complexity Analysis
Time Complexity
O(n + E)
Space Complexity
O(n)
Where E is the number of trust relationships.
- Time — one pass over the edges plus one pass over the people.
- Space — a single array of
n + 1integers. Using two separate degree arrays would work identically but doubles the memory for no benefit.
Edge Cases
Related Problems
- Binary Tree Level Order Traversal — BFS, for graph problems that genuinely need traversal
- Contains Duplicate — counting rather than searching
- Number of Good Pairs — another problem solved purely by accumulating counts