Find the Town Judge
In this lab, you are tasked with finding the town judge among n
people in a town. The people in the town are labeled from 1
to n
. There is a rumor going on that one of them is a secretly the town judge. In order to identify the town judge, you have to consider the following conditions:
- The town judge trusts nobody.
- Everybody (except for the town judge) trusts the town judge.
- There is exactly one person that satisfies properties 1 and 2.
You will be provided an array trust
, where trust[i] = [ai, bi]
signifies that the person labeled ai
trusts the person labeled bi
. If a trust relationship is not present in the trust
array, it means that such a trust relationship does not exist.
Your task is to return the label of the town judge if the town judge exists and can be identified or return -1
if the judge does not exist or cannot be identified.
Examples
-
Input: n = 2, trust = [[1,2]]
Output: 2
In this case, there are two people in the town, person1
and person2
. The trust array indicates that person1
trusts person2
. We can safely assume that person2
is the town judge as they satisfy all the given conditions: person2
trusts nobody, and everybody (except the town judge) trusts person2
. -
Input: n = 3, trust = [[1,3],[2,3]]
Output: 3
In this scenario, the trust array tells us that person1
trusts person3
and person2
trusts person3
. Only person3
satisfies the conditions to be a town judge as no one trusts3
in the trust array, and everybody except3
trusts them. -
Input: n = 3, trust = [[1,3],[2,3],[3,1]]
Output: -1
Here, person1
trusts person3
, person2
trusts person3
, and person3
trusts person1
. In this case, no one can be identified as the town judge as none of them satisfy all the required conditions.
Constraints
1 <= n <= 1000
0 <= trust.length <= 104
trust[i].length == 2
- All the pairs of
trust
are unique. ai != bi
1 <= ai, bi <= n