Find the Town Judge: Graph Degree Counting
In a town of n people labeled 1 to n, exactly one person is the town judge. The town judge trusts nobody. Everybody else (all n-1 other people) trusts the judge. You are given an array trust where each element [a, b] means person a trusts person b. Find the town judge, or return -1 if no judge exists.
This is LeetCode 997: Find the Town Judge, and it is a perfect introduction to graph degree counting. You do not need DFS or BFS here. The problem reduces to a simple observation about in-degrees and out-degrees in a directed trust graph.
Why this problem matters
Find the Town Judge is one of the cleanest introductions to thinking about graphs in terms of degrees. Many harder graph problems (topological sort, cycle detection, Euler paths) rely on counting in-degrees and out-degrees as a first step. This problem isolates that concept in the simplest possible setting: find the one node that has a specific degree signature.
It also teaches you to avoid overcomplicating things. Your first instinct might be to build an adjacency list and run a graph traversal. But the degree counting approach solves it in one pass through the trust array with no graph construction at all.
The key insight
Think of each trust pair [a, b] as a directed edge from a to b. The town judge has two properties:
- In-degree = n-1: everyone else trusts the judge, so
n-1arrows point toward the judge. - Out-degree = 0: the judge trusts nobody, so zero arrows leave the judge.
You could track in-degrees and out-degrees separately with two arrays. But there is a cleaner trick: use a single "trust score" array. For each pair [a, b], decrement person a's score by 1 (they trust someone) and increment person b's score by 1 (they are trusted). The judge ends up with a trust score of exactly n-1, because they receive n-1 increments and zero decrements.
The solution
def find_judge(n: int, trust: list[list[int]]) -> int:
score = [0] * (n + 1)
for a, b in trust:
score[a] -= 1
score[b] += 1
for i in range(1, n + 1):
if score[i] == n - 1:
return i
return -1
The score array is sized n+1 so that person labels (1 through n) map directly to indices. We loop through every trust pair once, updating both the truster and the trusted person. Then we scan through all people to find the one with score n-1.
Why does score[i] == n-1 identify the judge? The judge is trusted by all n-1 others, giving them n-1 increments. The judge trusts nobody, so they get zero decrements. Their net score is n-1. Any non-judge person has at least one decrement (they trust the judge), so their score is at most n-2. The only way to reach n-1 is to be trusted by everyone and trust nobody.
Instead of maintaining separate in-degree and out-degree arrays, combine them into one trust score. For each pair [a, b], do score[a] -= 1 and score[b] += 1. The judge is the person with score exactly n-1. This saves space and keeps the code minimal.
Visual walkthrough
Step 1: Count trust relationships for each person
For each trust pair [a, b], person a has out-degree +1 (they trust someone) and person b has in-degree +1 (they are trusted). We can combine these into a single trust score: being trusted adds +1, trusting someone adds -1.
| Person | In-degree | Out-degree | Trust score |
|---|---|---|---|
| 1 | 0 | 1 | -1 |
| 2 | 0 | 1 | -1 |
| 3 | 2 | 0 | 2 |
Trust pairs: [1,3] and [2,3]. Person 3 is trusted by both 1 and 2, but trusts nobody.
Step 2: Find the person with trust score = n - 1
The judge is trusted by all n-1 other people (in-degree = n-1) and trusts nobody (out-degree = 0). That means the judge's trust score is exactly (n-1) - 0 = n-1. With n=3, we look for trust score = 2.
| Person | Trust score | = n-1? |
|---|---|---|
| 1 | -1 | No |
| 2 | -1 | No |
| 3 | 2 | Yes |
Person 3 has trust score 2 = n-1. Person 3 is the town judge.
The trust score trick works because the judge is the only person who never appears as the first element in any trust pair (out-degree = 0) and appears as the second element in exactly n-1 pairs (in-degree = n-1). The combined score captures both conditions in a single number.
Complexity analysis
| Approach | Time | Space |
|---|---|---|
| Degree counting | O(n + t) | O(n) |
Here t is the number of trust pairs.
Time: We loop through the t trust pairs once to build the score array, then loop through n people to find the judge. Total: O(n + t).
Space: The score array has n+1 entries. No other data structures are needed. Total: O(n).
The building blocks
1. In-degree and out-degree counting
The foundational graph concept here is degree counting. In a directed graph, each node has an in-degree (how many edges point to it) and an out-degree (how many edges leave it). Many graph algorithms start by computing degrees. Topological sort (Kahn's algorithm) peels off nodes with in-degree 0. Euler path algorithms check degree conditions. This problem drills the degree counting step in isolation.
in_deg = [0] * (n + 1)
out_deg = [0] * (n + 1)
for a, b in edges:
out_deg[a] += 1
in_deg[b] += 1
2. Single-pass trust score
The optimization of combining in-degree and out-degree into one value is a pattern that shows up whenever you need to find a node with a specific degree signature. Instead of two arrays, you use one array and encode the difference. This is the same idea behind "net flow" in network problems: what matters is the balance between incoming and outgoing, not the individual counts.
score = [0] * (n + 1)
for a, b in edges:
score[a] -= 1
score[b] += 1
Edge cases
- n=1 with no trust pairs: there is only one person and nobody needs to trust them. They are the judge by default. The score array has
score[1] = 0, andn-1 = 0, soscore[1] == n-1is true. Returns 1 correctly. - No judge exists: if two people both have out-degree 0, neither can be the judge (the judge must be trusted by everyone, but if two people trust nobody, at least one of them is not trusted by all others). The score check naturally handles this because at most one person can have score
n-1. - Everyone trusts the same person but that person also trusts someone: their score is
n-2(they getn-1increments but one decrement), so they are correctly rejected. - Trust pairs form a cycle: for example,
[[1,2],[2,1]]withn=2. Both people have score 0, notn-1 = 1. Returns -1 correctly.
From understanding to recall
You have seen how the trust score trick reduces this problem to a single pass and a scan. The logic is clean. But can you reproduce it from memory when you see a similar degree-based graph problem in an interview?
The details that trip people up: using n+1 for the array size, remembering to decrement the truster and increment the trusted, and checking for n-1 (not n). These are small things, but under pressure they matter.
Spaced repetition makes these details automatic. You practice writing the score loop and the scan from scratch at increasing intervals. After a few rounds, the pattern flows out without hesitation. You do not need to re-derive it. You just write it.
Related posts
- Course Schedule - Uses in-degree counting in Kahn's algorithm for topological sort, the natural next step after this problem
- Number of Provinces - Graph connectivity via DFS/Union-Find, showing a different way to analyze graph structure
- Clone Graph - Graph traversal with hash map tracking, another fundamental graph pattern to pair with degree counting
CodeBricks breaks Find the Town Judge into its degree-counting and score-scanning building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a degree-based graph problem shows up in your interview, you do not hesitate. You just write it.