Graphs · LC #997
Find the Town Judge
In a town of n people, find the judge who is trusted by everyone else and trusts nobody, using net in/out-degree scoring.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
In a town of `n` people labeled 1 to n, one person is the **town judge** if: 1. The town judge trusts nobody. 2. Everybody (except the judge) trusts the town judge. Given `trust` as an array of pairs `[a, b]` meaning "a trusts b", return the label of the town judge, or -1 if no such person exists.
Sample I/O
Input: n=3, trust=[[1,3],[2,3]] Output: 3 Input: n=3, trust=[[1,3],[2,3],[3,1]] Output: -1 Input: n=1, trust=[] Output: 1
Time: O(T+n) · Space: O(n)
Intuition
How to Think About It
Intuition
Model the problem as a directed graph. The judge has in-degree n-1 (everyone trusts them) and out-degree 0 (they trust nobody). Tracking a single "net trust score" (+1 for being trusted, -1 for trusting) collapses both conditions into one check: score == n-1.
Core Concept
Net-degree array. For each trust pair [a, b]: decrement score[a] (a trusts someone) and increment score[b] (b is trusted). The judge is the unique person with score == n-1.
When to use
When a graph problem reduces to counting in/out degrees per node; when you need to identify a special node satisfying a universal trust/dependency constraint.
When NOT to use
When the graph has multiple special nodes, multiple components, or the trust relationship is not binary/directed - more complex traversal needed.
Key Insights
What to Know Cold
- Combining in-degree and out-degree into one net score eliminates needing two separate arrays.
- If n == 1 and trust is empty, person 1 is trivially the judge (no one else to distrust).
- Score n-1 uniquely identifies the judge because no two people can both have score n-1 in a valid input.
- This is essentially finding a "sink" node in a functional graph with one extra uniqueness constraint.
- Time complexity is linear in the number of trust pairs - no adjacency list traversal needed.
1 example
Worked Examples
Net-score linear scan
n=3, trust=[[1,3],[2,3]] - person 3 is trusted by 1 and 2, trusts nobody.
Build score array, apply trust pairs, scan for score == n-1.
function findJudge(n: number, trust: number[][]): number {
const score = new Array(n + 1).fill(0);
for (const [a, b] of trust) { score[a]--; score[b]++; }
for (let i = 1; i <= n; i++) if (score[i] === n - 1) return i;
return -1;
}Output: 3
Demonstrates in/out-degree analysis - a recurring graph pattern. Interviewers check whether you model this as a graph problem vs brute-forcing with sets.