Find the Town Judge

Difficulty: Easy Source: NeetCode

Problem

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:

1. The town judge trusts nobody.
2. Everybody else (except possibly the judge) trusts the town judge.
3. There is exactly one person who satisfies properties 1 and 2.

You are given an array trust where trust[i] = [a, b] means person a trusts person b. Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.

Example 1: Input: trust = [[1,3],[2,3]], n = 3 Output: 3

Example 2: Input: trust = [[1,3],[2,3],[3,1]], n = 3 Output: -1

Example 3: Input: trust = [[1,2]], n = 2 Output: 2

Constraints:

• 1 <= n <= 1000
• 0 <= trust.length <= 10^4
• trust[i].length == 2
• All the pairs in trust are unique
• a != b

Prerequisites

Before attempting this problem, you should be comfortable with:

• Graph in-degree / out-degree — counting how many edges point into or out of a node
• Hash Maps / Arrays — tracking counts per person

1. Brute Force

Intuition

For each person, check two things: do they trust anyone (out-degree > 0)? And is trusted by everyone else (in-degree == n-1)? The judge is the person with out-degree 0 and in-degree n-1. We can gather this by building the full trust sets and counting.

Algorithm

1. Build trusts_set[person] = set of people they trust.
2. Build trusted_by_count[person] = how many people trust them.
3. For each person p: if len(trusts_set[p]) == 0 and trusted_by_count[p] == n - 1, return p.
4. Return -1.

Solution

def findJudge(n: int, trust: list[list[int]]) -> int:
    trusts = [set() for _ in range(n + 1)]
    trusted_by = [0] * (n + 1)

    for a, b in trust:
        trusts[a].add(b)
        trusted_by[b] += 1

    for p in range(1, n + 1):
        if len(trusts[p]) == 0 and trusted_by[p] == n - 1:
            return p

    return -1


print(findJudge(3, [[1,3],[2,3]]))          # 3
print(findJudge(3, [[1,3],[2,3],[3,1]]))    # -1
print(findJudge(2, [[1,2]]))                # 2
print(findJudge(1, []))                     # 1

Complexity

• Time: O(T + N) where T = number of trust pairs
• Space: O(N + T)

2. In-Degree / Out-Degree Score

Intuition

We can compress both conditions into a single score per person: score[p] = in_degree[p] - out_degree[p]. The judge trusts nobody (out-degree 0) and is trusted by everyone else (in-degree n-1), so score[judge] = (n-1) - 0 = n-1. Any non-judge who trusts someone has out-degree ≥ 1, so their score is at most n-2. We just need to find the person whose score equals n-1.

Algorithm

1. Initialize score[1..n] = 0.
2. For each [a, b] in trust: score[a] -= 1 (trusts someone), score[b] += 1 (trusted by someone).
3. Return the person with score[p] == n - 1, or -1 if none.

Solution

def findJudge(n: int, trust: list[list[int]]) -> int:
    score = [0] * (n + 1)  # 1-indexed

    for a, b in trust:
        score[a] -= 1  # a trusts someone → out-degree
        score[b] += 1  # b is trusted → in-degree

    for p in range(1, n + 1):
        if score[p] == n - 1:
            return p

    return -1


print(findJudge(3, [[1,3],[2,3]]))          # 3
print(findJudge(3, [[1,3],[2,3],[3,1]]))    # -1
print(findJudge(2, [[1,2]]))                # 2
print(findJudge(1, []))                     # 1 (single person trusts nobody and is trusted by 0 = n-1 = 0 others)

Complexity

• Time: O(T + N) where T = number of trust pairs
• Space: O(N)

Common Pitfalls

The n=1 edge case. With one person and no trust pairs, that person is the judge — they trust nobody and are “trusted by everyone else” (vacuously true). The score approach handles this correctly since score[1] = 0 = n-1 = 0.

Mutual trust disqualifies both. If A trusts B and B trusts A, neither can be the judge. The score method handles this because both get a -1 for trusting someone.

1-indexed vs 0-indexed. People are labeled 1 to n. Allocate arrays of size n+1 and ignore index 0, or adjust accordingly.