Find the Town Judge

Easy
15.8% Acceptance

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:

  1. The town judge trusts nobody.
  2. Everybody (except for the town judge) trusts the town judge.
  3. 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

  1. Input: n = 2, trust = [[1,2]] Output: 2 In this case, there are two people in the town, person 1 and person 2. The trust array indicates that person 1 trusts person 2. We can safely assume that person 2 is the town judge as they satisfy all the given conditions: person 2 trusts nobody, and everybody (except the town judge) trusts person 2.

  2. Input: n = 3, trust = [[1,3],[2,3]] Output: 3 In this scenario, the trust array tells us that person 1 trusts person 3 and person 2 trusts person 3. Only person 3 satisfies the conditions to be a town judge as no one trusts 3 in the trust array, and everybody except 3 trusts them.

  3. Input: n = 3, trust = [[1,3],[2,3],[3,1]] Output: -1 Here, person 1 trusts person 3, person 2 trusts person 3, and person 3 trusts person 1. 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