LeetCode 997 - Find the Town Judge

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Graph Theory

Solution

Problem Understanding

The problem describes a town containing n people labeled from 1 to n. Among these people, there may exist a special person called the town judge.

The judge must satisfy two strict conditions:

The judge trusts nobody.
Every other person trusts the judge.

Additionally, the problem guarantees that if such a person exists, there can only be one judge.

The input consists of:

An integer n, representing the number of people.
A list called trust, where each element is a pair [a, b], meaning person a trusts person b.

The goal is to determine whether a valid judge exists. If one does, return that person's label. Otherwise, return -1.

The constraints are small to moderate:

n can be at most 1000
trust.length can be as large as 10^4

These limits are small enough that an O(n^2) solution would technically pass, but the problem has a much cleaner linear-time graph interpretation.

This problem is fundamentally about incoming and outgoing relationships in a directed graph:

Trusting someone is an outgoing edge.
Being trusted is an incoming edge.

A valid judge must therefore have:

Outdegree 0
Indegree n - 1

Several edge cases are important:

A town with only one person and no trust relationships. In this case, that single person is trivially the judge.
Cyclic trust relationships, where people trust each other. A judge cannot trust anyone.
Multiple highly trusted people. Only one person can satisfy all conditions.
Empty trust lists when n > 1. No judge can exist because nobody is trusted by everyone else.

The problem also guarantees that trust pairs are unique and ai != bi, which simplifies implementation because we never need to handle duplicate edges or self-trust.

Approaches

Brute Force Approach

A straightforward solution is to check every person individually and verify whether they satisfy the judge conditions.

For each candidate person:

Scan the entire trust array.
Ensure the candidate never appears as a truster.
Count how many people trust the candidate.
If the candidate trusts nobody and is trusted by exactly n - 1 people, return that candidate.

This works because the judge definition is explicit and easy to verify directly.

However, this approach is inefficient because for every person we may scan the entire trust list again. If there are n people and m trust relationships, the complexity becomes O(n * m).

With n = 1000 and m = 10000, this is still acceptable, but unnecessary.

Optimal Approach

The key insight is that the judge conditions can be represented using indegree and outdegree counts.

For every trust pair [a, b]:

a trusts someone, so a cannot be the judge.
b gains one additional person trusting them.

We can maintain:

outdegree[a] += 1
indegree[b] += 1

After processing all trust relationships, the judge is simply the person satisfying:

outdegree[i] == 0
indegree[i] == n - 1

This transforms the problem into a single pass over the edges and a single pass over the people.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(1)	Rechecks the trust list for every candidate
Optimal	O(n + m)	O(n)	Uses indegree and outdegree counting

Here, m represents trust.length.

Algorithm Walkthrough

Create two arrays of size n + 1:

indegree, to count how many people trust each person.
outdegree, to count how many people each person trusts.

We use n + 1 because people are labeled starting from 1, not 0. 2. Iterate through every trust relationship [a, b].

For each pair:

Increment outdegree[a] because person a trusts someone.
Increment indegree[b] because person b is trusted by someone.

After processing all trust relationships, iterate through all people from 1 to n.
For each person:

Check whether outdegree[person] == 0
Check whether indegree[person] == n - 1

If both conditions are true, this person satisfies the judge definition. 5. Return the matching person immediately. 6. If no person satisfies both conditions, return -1.

Why it works

The algorithm directly models the mathematical definition of the judge.

A judge must trust nobody, which means their outgoing trust count must be zero.

A judge must be trusted by everyone else, which means their incoming trust count must equal n - 1.

Because we compute these counts exactly once for every trust relationship, the final scan correctly identifies the only possible judge. If no person satisfies both conditions simultaneously, then no judge exists.

Python Solution

from typing import List

class Solution:
    def findJudge(self, n: int, trust: List[List[int]]) -> int:
        indegree = [0] * (n + 1)
        outdegree = [0] * (n + 1)

        for a, b in trust:
            outdegree[a] += 1
            indegree[b] += 1

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

        return -1

The implementation closely follows the algorithm described earlier.

The two arrays, indegree and outdegree, store how many trust relationships point into and out of each person. Since people are labeled starting at 1, index 0 is unused.

The loop over trust processes each relationship exactly once. Whenever [a, b] appears:

a gains an outgoing edge
b gains an incoming edge

After all relationships are processed, the second loop checks each person against the judge conditions.

The first person whose indegree equals n - 1 and whose outdegree equals 0 is returned immediately.

If no valid candidate is found, the function returns -1.

Go Solution

func findJudge(n int, trust [][]int) int {
    indegree := make([]int, n+1)
    outdegree := make([]int, n+1)

    for _, relation := range trust {
        a := relation[0]
        b := relation[1]

        outdegree[a]++
        indegree[b]++
    }

    for person := 1; person <= n; person++ {
        if indegree[person] == n-1 && outdegree[person] == 0 {
            return person
        }
    }

    return -1
}

The Go implementation is nearly identical to the Python version.

Slices are used instead of Python lists. The arrays are initialized using make([]int, n+1).

Go does not require special handling for integer overflow here because all values are small and well within the range of the standard int type.

The trust relationships are iterated using Go's range syntax.

Worked Examples

Example 1

Input: n = 2, trust = [[1,2]]

Initial state:

Person	indegree	outdegree
1	0	0
2	0	0

Process [1,2]:

Person 1 trusts someone
Person 2 gains one incoming trust

Updated state:

Person	indegree	outdegree
1	0	1
2	1	0

Now check conditions:

Person 1:
indegree = 0
outdegree = 1
Not a judge
Person 2:
indegree = 1 = n - 1
outdegree = 0
Valid judge

Answer:

Example 2

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

Initial state:

Person	indegree	outdegree
1	0	0
2	0	0
3	0	0

Process [1,3]:

Person	indegree	outdegree
1	0	1
2	0	0
3	1	0

Process [2,3]:

Person	indegree	outdegree
1	0	1
2	0	1
3	2	0

Check candidates:

Person 1 fails because outdegree is 1
Person 2 fails because outdegree is 1
Person 3:
indegree = 2 = n - 1
outdegree = 0

Answer:

Example 3

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

Process all trust relationships:

Person	indegree	outdegree
1	1	1
2	0	1
3	2	1

Now evaluate:

Person 1 trusts someone
Person 2 trusts someone
Person 3 trusts someone

Since every person has outdegree greater than zero, nobody can be the judge.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	One pass through trust relationships and one pass through all people
Space	O(n)	Two arrays of size `n + 1`

The algorithm is linear in the size of the input.

Processing all trust relationships takes O(m) time, where m = trust.length.

Checking all people afterward takes O(n) time.

The additional memory usage comes from the indegree and outdegree arrays.

Test Cases

solution = Solution()

# Provided examples
assert solution.findJudge(2, [[1, 2]]) == 2  # Simple valid judge
assert solution.findJudge(3, [[1, 3], [2, 3]]) == 3  # Judge trusted by everyone
assert solution.findJudge(3, [[1, 3], [2, 3], [3, 1]]) == -1  # Judge trusts someone

# Single person town
assert solution.findJudge(1, []) == 1  # Single person is trivially the judge

# No trust relationships with multiple people
assert solution.findJudge(3, []) == -1  # Nobody trusted by everyone

# Multiple trust chains
assert solution.findJudge(4, [[1, 3], [2, 3], [4, 3]]) == 3  # Valid judge in larger town

# Candidate trusts someone
assert solution.findJudge(4, [[1, 3], [2, 3], [3, 4]]) == -1  # Candidate invalidated

# Everyone trusts different people
assert solution.findJudge(4, [[1, 2], [2, 3], [3, 4]]) == -1  # No universal trusted person

# Judge with maximum incoming edges
assert solution.findJudge(5, [[1, 5], [2, 5], [3, 5], [4, 5]]) == 5  # Fully trusted judge

# Cyclic trust
assert solution.findJudge(3, [[1, 2], [2, 3], [3, 1]]) == -1  # Cycle prevents judge

# Large but simple structure
assert solution.findJudge(6, [[1, 6], [2, 6], [3, 6], [4, 6], [5, 6]]) == 6  # Larger valid case

Test	Why
`n=2, [[1,2]]`	Smallest non-trivial valid case
`n=3, [[1,3],[2,3]]`	Standard valid judge example
`n=3, [[1,3],[2,3],[3,1]]`	Candidate invalidated by trusting someone
`n=1, []`	Single-person edge case
`n=3, []`	No trust relationships
`n=4, [[1,3],[2,3],[4,3]]`	Judge trusted by all others
`n=4, [[1,3],[2,3],[3,4]]`	Highly trusted person still trusts someone
`n=4, [[1,2],[2,3],[3,4]]`	No universal trust target
`n=5, ... -> 5`	Maximum incoming trust
Cyclic trust case	Ensures cycles do not produce false positives

Edge Cases

Single Person Town

When n = 1 and the trust list is empty, the only person in the town automatically satisfies the judge conditions.

They trust nobody, because there are no trust relationships.

They are also trusted by everyone else vacuously, because there are no other people.

A common mistake is returning -1 whenever the trust list is empty. The implementation avoids this by checking indegree and outdegree conditions directly.

Candidate Trusted by Everyone but Trusts Someone

A person may appear to be the judge because everyone trusts them, but if they trust even one other person, they immediately become invalid.

For example:

n = 3
trust = [[1,3],[2,3],[3,1]]

Person 3 is trusted by two people, but also trusts person 1.

The implementation correctly catches this because it separately tracks outdegree and requires it to equal zero.

No Universal Trusted Person

Another tricky situation occurs when trust relationships exist, but no single person is trusted by all others.

For example:

n = 4
trust = [[1,2],[2,3],[3,4]]

Every person is trusted by at most one other person.

A naive solution might incorrectly return the person with the highest trust count. The implementation avoids this by requiring indegree to be exactly n - 1.

Multiple People with High Trust Counts

Several people may receive many incoming trust relationships, but only one can satisfy the full judge conditions.

For example:

n = 4
trust = [[1,3],[2,3],[1,4],[2,4]]

Both persons 3 and 4 are trusted by two people, but neither is trusted by all three others.

The implementation ensures correctness by checking for the exact required indegree value rather than selecting the maximum.