Find the Town Judge

Determine who is trusted by everyone and trusts no one in a town.

graph indegree outdegree

In a town, there are n people labeled from 1 to n. A rumor claims that one person is the town judge. The town judge exists if and only if:

1. The town judge trusts nobody.
2. Everybody (except the town judge) trusts the town judge.

You are given an integer n representing the number of people and a 2D integer array trust where each element trust[i] = [a, b] means that person a trusts person b.

Write a function `find_judge(n: int, trust: list[list[int]]) -> int` that returns the label of the town judge if they exist, otherwise returns -1.

Constraints

1 <= n <= 1000
0 <= trust.length <= 10^4
All trust pairs are unique.
1 <= a, b <= n
a != b

Example

>>> find_judge(2, [[1,2]])
2
>>> find_judge(3, [[1,3],[2,3]])
3
>>> find_judge(3, [[1,3],[2,3],[3,1]])
-1
>>> find_judge(1, [])
1

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Think of trust as a directed graph: a -> b means a trusts b. Count how many people trust each person and how many people each person trusts.

The judge must be trusted by n-1 people and must trust 0 people.

Initialize two arrays of size n+1 (ignore index 0) to track indegree and outdegree. Iterate over trust and update both arrays. Finally, check every person for the condition.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.