LeetCode 997: Find the Town Judge

The problem. In a town of n people labelled 1 to n, there is a rumour that one of them is secretly the town judge.

If the judge exists, then:

1. The judge trusts nobody.
2. Everybody else trusts the judge.
3. There is exactly one person satisfying both.

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        (person 3 trusts someone, so cannot be the judge)

#The reframe that solves it

The three conditions look like three separate things to check. They are not. Model the town as a directed graph — each person is a node, each trust relationship an edge pointing from truster to trusted — and the whole problem becomes arithmetic.

For any person:

• out-degree = how many people they trust
• in-degree = how many people trust them

Now restate the conditions:

1. The judge trusts nobody → out-degree = 0
2. Everybody else trusts them → in-degree = n − 1

And that is the entire problem. The judge is the unique person whose in-degree minus out-degree equals n − 1.

#Solution 1 — two counting arrays

The direct translation:

def findJudge(n, trust):
    if n == 1:
        return 1                      # nobody to trust, nobody to distrust

    trusts_count  = [0] * (n + 1)     # out-degree
    trusted_count = [0] * (n + 1)     # in-degree

    for a, b in trust:
        trusts_count[a] += 1
        trusted_count[b] += 1

    for person in range(1, n + 1):
        if trusts_count[person] == 0 and trusted_count[person] == n - 1:
            return person

    return -1

• Time: O(E + n), where E is the number of trust pairs.
• Space: O(n) for the two arrays.

Two things to note.

[0] * (n + 1), not [0] * n. People are labelled 1 to n, so we waste index 0 in exchange for never writing person - 1 anywhere. That trade is almost always worth making — off-by-one errors in index translation are a classic interview stumble.

The n == 1 guard. With one person and an empty trust array, that person is trivially the judge: they trust nobody (out-degree 0) and everybody else — all zero of them — trusts them (in-degree 0 = n − 1). The general code actually handles this correctly, but stating the edge case explicitly shows you looked for it.

#Solution 2 — a single balance array

Since we only ever compare in - out, we can track one number instead of two:

def findJudge(n, trust):
    balance = [0] * (n + 1)

    for a, b in trust:
        balance[a] -= 1     # a trusts someone: worse candidate
        balance[b] += 1     # b is trusted: better candidate

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

    return -1

Same complexity, half the memory, and it reads better once you see the idea: every edge makes the source less judge-like and the target more judge-like. The judge is the only person who can reach n − 1.

#Why can only one person reach n − 1?

Worth being ready for, because interviewers ask.

To have a balance of n − 1, a person needs in-degree n − 1 and out-degree 0 — the maximum possible in-degree with the minimum possible out-degree. Suppose two people, X and Y, both had balance n − 1. Then X has in-degree n − 1, meaning everyone except X trusts them — including Y. So Y's out-degree is at least 1, giving Y a balance of at most n − 2. Contradiction.

So the moment you find someone at n − 1, you can return immediately. No second candidate is possible.

#The early exit

There is a cheap rejection worth mentioning:

def findJudge(n, trust):
    if len(trust) < n - 1:
        return -1           # not enough edges for anyone to be trusted by all

    balance = [0] * (n + 1)
    for a, b in trust:
        balance[a] -= 1
        balance[b] += 1

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

If a judge exists, at least n − 1 trust relationships must exist — one from each non-judge. Fewer than that and the answer is definitively -1. It does not change the asymptotic complexity, but it is a correct observation about the problem's structure, and interviewers notice those.

#What NOT to do

The instinct many people have is to check each person against every trust pair:

# O(n × E) — avoid
def findJudge(n, trust):
    for person in range(1, n + 1):
        trusts_nobody = all(a != person for a, b in trust)
        trusted_by_all = sum(1 for a, b in trust if b == person) == n - 1
        if trusts_nobody and trusted_by_all:
            return person
    return -1

It is correct, and it rescans the entire trust list for every person. With n = 1000 and 10,000 trust pairs, that is ten million operations instead of eleven thousand.

#Test cases to run

The two that catch people are n = 1 with an empty list, and the case where a plausible candidate also trusts somebody. Both are handled correctly by the balance solution — which is a good argument for its elegance.

#Other languages

function findJudge(n, trust) {
  const balance = new Array(n + 1).fill(0);
  for (const [a, b] of trust) {
    balance[a]--;
    balance[b]++;
  }
  for (let i = 1; i <= n; i++) {
    if (balance[i] === n - 1) return i;
  }
  return -1;
}

function findJudge(int $n, array $trust): int {
    $balance = array_fill(0, $n + 1, 0);
    foreach ($trust as [$a, $b]) {
        $balance[$a]--;
        $balance[$b]++;
    }
    for ($i = 1; $i <= $n; $i++) {
        if ($balance[$i] === $n - 1) return $i;
    }
    return -1;
}

#The transferable lesson

Problems phrased in social terms — trust, following, recommending, reporting-to, friendship — are almost always graph problems wearing a costume. When you see one, immediately ask:

• Are the relationships directed or undirected?
• Does the answer depend on how many edges point in or out?
• Is it about reachability (BFS/DFS), cycles, or just degree counting?

Town Judge is pure degree counting, which is why it is Easy. But the reframe is the same one that unlocks Course Schedule (cycle detection), Find the Celebrity (almost identical to this problem), and Minimum Number of Vertices to Reach All Nodes (in-degree zero).

#Key takeaways

• "Everyone trusts X, X trusts nobody" is a statement about in-degree and out-degree.
• Track a single balance (+1 trusted, −1 trusting) instead of two arrays.
• The judge is the unique person with balance n − 1 — and you can prove uniqueness.
• Size arrays n + 1 when labels are 1-indexed. Cheaper than translating indexes everywhere.
• If your loop rescans data you have already seen, count it once instead.
• Social-relationship problems are graph problems. Name the structure out loud.