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
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[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.
Input: n = 2, trust = [[1,2]] Output: 2 In this case, there are two people in the town, person
2. The trust array indicates that person
2. We can safely assume that person
2is the town judge as they satisfy all the given conditions: person
2trusts nobody, and everybody (except the town judge) trusts person
Input: n = 3, trust = [[1,3],[2,3]] Output: 3 In this scenario, the trust array tells us that person
3. Only person
3satisfies the conditions to be a town judge as no one trusts
3in the trust array, and everybody except
Input: n = 3, trust = [[1,3],[2,3],[3,1]] Output: -1 Here, person
3, and person
1. In this case, no one can be identified as the town judge as none of them satisfy all the required conditions.
1 <= n <= 1000
0 <= trust.length <= 104
trust[i].length == 2
- All the pairs of
ai != bi
1 <= ai, bi <= n