Find the Town Judge

How it works

We can combine the two arrays into one by using the difference: delta[i] = incoming[i] - outgoing[i]. The judge has n - 1 people trusting them and trusts 0 people, so their delta equals (n - 1) - 0 = n - 1. Anyone who trusts at least one person will have a delta less than n - 1.

Steps

1. Create a single array delta of size n + 1.
2. For each trust pair [a, b]:
   • Decrement delta[a] (person a trusts someone, reducing their score).
   • Increment delta[b] (person b is trusted, increasing their score).
3. Iterate through persons 1 to n:
   • If delta[i] == n - 1, return i.
4. Return -1 if no judge found.

Complexity

• Time complexity: O(V + E)
• Space complexity: O(V)

Where V is the number of vertices and E is the number of edges.

Things to watch for

Only Checking Indegree Without Outdegree

The town judge must be trusted by everyone (indegree = n-1) AND trust nobody (outdegree = 0). A common mistake is only checking that someone is trusted by n-1 people, which would incorrectly identify a person who also trusts others.

Off-by-One Errors with 1-Indexed People

People are labeled from 1 to n, not 0 to n-1. When using arrays indexed from 0, forgetting to iterate from 1 to n (inclusive) or incorrectly accessing array indices can cause out-of-bounds errors or missed candidates.

from typing import List
from collections import defaultdict

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        delta = defaultdict(int)

        for src, dst in trust:
            delta[src] -= 1
            delta[dst] += 1

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

        return -1

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        vector<int> delta(n + 1, 0);

        for (auto& t : trust) {
            delta[t[0]]--;
            delta[t[1]]++;
        }

        for (int i = 1; i <= n; i++) {
            if (delta[i] == n - 1) {
                return i;
            }
        }

        return -1;
    }
};