Find The Town Judge

Function Name: findJudge

Description

In a town, there are N people labeled from 1 to N. There is a rumor that one of these people is secretly the town judge.

If the town judge exists, then:

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 are given an array `trust` where `trust[i] = [a, b]` represents that the person labeled `a` trusts the person labeled `b`.

Write a function `findJudge` that finds the town judge's label.

The function should take in the parameter `N`, the number of people, and an array of trust pairs, and should return the label of the town judge if they exist or `-1` if they do not.

Requirements

• The function must handle up to 1000 people.
• The trust array may contain up to 10,000 pairs.
• No individual trusts themselves, i.e., there are no pairs where `a == b` in the trust array.
• Trust relationships are not necessarily reciprocal.
• Trust relationships are not transitive.
• Function must have a time complexity better than O(n^2).

Examples

Example 1:Input: N = 2, trust = [[1, 2]]Output: 2Explanation: Person 1 trusts person 2, but person 2 does not trust anyone, hence person 2 is the town judge.Example 2:Input: N = 3, trust = [[1, 3], [2, 3]]Output: 3Explanation: Person 1 and person 2 both trust person 3, but person 3 does not trust anyone, hence person 3 is the town judge.Example 3:Input: N = 3, trust = [[1, 3], [2, 3], [3, 1]]Output: -1Explanation: Person 3 trusts someone (person 1), thus they cannot be the town judge.

Links