LeetCode 997: Find the Town Judge

Problem Restatement

There are n people in a town labeled from 1 to n.

We are given an array trust, where each pair:

[a, b]

means person a trusts person b.

We need to find the town judge.

If the judge exists, then:

If no judge can be identified, return -1.

The official constraints include 1 <= n <= 1000, 0 <= trust.length <= 10^4, all trust pairs are unique, and a != b.

Input and Output

Function shape:

def findJudge(n: int, trust: list[list[int]]) -> int:
    ...

Examples

Example 1:

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

Person 1 trusts person 2.

Person 2 trusts nobody.

Everyone except person 2 trusts person 2.

Answer:

2

Example 2:

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

Persons 1 and 2 both trust person 3.

Person 3 trusts nobody.

Answer:

3

Example 3:

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

Person 3 is trusted by 1 and 2, but person 3 trusts person 1.

So person 3 cannot be the judge.

Answer:

-1

First Thought: Check Each Person

A direct solution is to test every person as a judge candidate.

For a candidate person, check all trust pairs:

1. If person appears as the first value, then they trust someone, so they cannot be judge.
2. Count how many people trust person.
3. If that count is n - 1, then person is the judge.

class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        for person in range(1, n + 1):
            trusts_someone = False
            trusted_by = 0

            for a, b in trust:
                if a == person:
                    trusts_someone = True
                    break

                if b == person:
                    trusted_by += 1

            if not trusts_someone and trusted_by == n - 1:
                return person

        return -1

This works, but it repeats the same scan for every person.

Problem With Repeated Scanning

If there are n people and m trust pairs, the direct solution costs:

O(n * m)

We can do better by counting incoming and outgoing trust once.

Key Insight

The town judge has a very specific graph shape.

For each pair [a, b]:

a trusts b

So:

outgoing[a] += 1
incoming[b] += 1

After processing all pairs, the judge is the person whose outgoing count is 0 and incoming count is n - 1.

Algorithm

Create two arrays of size n + 1:

incoming
outgoing

Then process every pair [a, b]:

1. Increment outgoing[a].
2. Increment incoming[b].

Then scan people from 1 to n.

Return the person i such that:

outgoing[i] == 0 and incoming[i] == n - 1

If no such person exists, return -1.

Correctness

For each trust pair [a, b], the algorithm records one outgoing trust for a and one incoming trust for b.

Therefore, after all pairs are processed, outgoing[i] is exactly the number of people that person i trusts, and incoming[i] is exactly the number of people who trust person i.

A town judge must trust nobody, so their outgoing count must be 0.

A town judge must be trusted by everybody else, so their incoming count must be n - 1.

The algorithm checks exactly these two conditions for every person. If it returns a person, that person satisfies the definition of town judge. If no person satisfies both conditions, no town judge exists.

Complexity

Let m = len(trust).

Implementation

class Solution:
    def findJudge(self, n: int, trust: list[list[int]]) -> int:
        incoming = [0] * (n + 1)
        outgoing = [0] * (n + 1)

        for a, b in trust:
            outgoing[a] += 1
            incoming[b] += 1

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

        return -1

Code Explanation

We create arrays indexed by person label:

incoming = [0] * (n + 1)
outgoing = [0] * (n + 1)

Index 0 is unused because people are labeled from 1 to n.

For every trust pair:

for a, b in trust:

person a trusts someone:

outgoing[a] += 1

person b is trusted by someone:

incoming[b] += 1

Then we check every person:

for person in range(1, n + 1):

The judge must satisfy both count conditions:

if outgoing[person] == 0 and incoming[person] == n - 1:

If no person satisfies them, return -1.

Alternative: One Score Array

We can combine incoming and outgoing counts into one score.

For each trust pair [a, b]:

score[a] -= 1
score[b] += 1

The judge has score n - 1, because they receive trust from n - 1 people and give trust to nobody.

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

        for a, b in trust:
            score[a] -= 1
            score[b] += 1

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

        return -1

This has the same time and space complexity, but uses one array instead of two.

Testing

def run_tests():
    s = Solution()

    assert s.findJudge(2, [[1, 2]]) == 2
    assert s.findJudge(3, [[1, 3], [2, 3]]) == 3
    assert s.findJudge(3, [[1, 3], [2, 3], [3, 1]]) == -1
    assert s.findJudge(1, []) == 1
    assert s.findJudge(4, [[1, 3], [2, 3], [4, 3]]) == 3
    assert s.findJudge(3, []) == -1

    print("all tests passed")

run_tests()