Find the Town Judge — Solution

Problem

In a town of n people labeled 1 through n, some people trust others. Given a list of [a, b] pairs meaning "person a trusts person b," find the town judge: the one person who trusts nobody but is trusted by everyone else. Return the judge's label, or -1 if no judge exists.

• Input: n = 4, trust = [[1,3],[1,4],[2,3],[2,4],[4,3]]
• Output: 3
• Explanation: Person 3 is trusted by persons 1, 2, and 4, and trusts no one themselves.

Counter-example: n = 3, trust = [[1,3],[2,3],[3,1]] → -1, because person 3 trusts person 1, disqualifying them as judge even though two people trust them.

Intuition

Model trust as directed edges: a → b means "a trusts b." The judge is the unique node with in-degree exactly n-1 (every other person points to them) and out-degree exactly 0 (they point to no one). A single pass over the trust list to count these degrees is all you need — no traversal required.

Solution — In/Out Degree Counting

Track two values per person: how many trust them (in-degree) and how many they trust (out-degree). The judge is the only person with in-degree n-1 and out-degree 0.

1. Initialize in_degree and out_degree arrays of size n+1 to zero (1-indexed to match person labels).
2. For each pair (truster, trusted), increment out_degree[truster] and in_degree[trusted].
3. Scan persons 1 to n; return the first with out_degree == 0 and in_degree == n-1.
4. Return -1 if no such person exists.

1def findJudge(n: int, trust: list[list[int]]) -> int:
2    in_degree = [0] * (n + 1)
3    out_degree = [0] * (n + 1)
4
5    for truster, trusted in trust:
6        out_degree[truster] += 1  # this person gives trust to someone
7        in_degree[trusted] += 1  # this person receives trust
8
9    for person in range(1, n + 1):
10        # judge trusts nobody and is trusted by everyone else
11        if out_degree[person] == 0 and in_degree[person] == n - 1:
12            return person
13
14    return -1

Time: O(n + t) — one pass through t trust pairs to build degrees, one pass through n people to find the judge. Space: O(n) — two arrays of size n+1 for in- and out-degrees.

Complexity Summary

Common Mistakes

• Checking only in-degree: A person trusted by n-1 others could still trust someone — you must also verify out_degree == 0 or the answer is wrong. The counter-example above illustrates this failure mode.
• Off-by-one on the in-degree threshold: The judge must be trusted by exactly n-1 people (everyone except themselves), not n. Checking >= n-1 would incorrectly pass someone trusted by all n if that were possible.
• 0-indexed arrays with 1-indexed people: Allocating size n and indexing by person label collides person n with index n, corrupting its count. Always allocate size n+1.
• Forgetting to return -1: The problem guarantees at most one judge, but not that one always exists. A missing return at the end causes undefined behavior or a wrong answer.
• Assuming n=1 is a special case: If n=1 and trust=[], the algorithm correctly returns 1 — in-degree is 0 = n-1 and out-degree is 0, so person 1 is vacuously the judge with no one else in town.

Related Problems

• course-schedule — directed graph where you detect cycles among dependency edges, a different use of in/out degree reasoning
• number-of-provinces — finding how many disconnected components exist in an undirected trust-like graph
• find-if-path-exists-in-graph — basic graph reachability via BFS or DFS over the same edge-list format
• evaluate-division — graph edges carry numeric weights; finding a value requires traversing paths rather than counting degrees
• all-paths-from-source-to-target — enumerate all paths in a directed acyclic graph using DFS with backtracking