Find the Town Judge - LeetCode
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:
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 are given an array trust where trust[i] = [ai, bi] representing that the person labeled ai trusts the person labeled bi. Return the label of the town judge if the town judge exists and can be identified, or return -1 otherwise.
Example 1: Input: n = 2, trust = [[1,2]] Output: 2 Example 2: Input: n = 3, trust = [[1,3],[2,3]] Output: 3 Example 3: Input: n = 3, trust = [[1,3],[2,3],[3,1]] Output: -1
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
- code
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
if not trust:
if n == 1: return 1
return -1
person = defaultdict(list)
for p, trusted in trust:
person[p].append(trusted)
judges = set(list(range(1, n+1))) - person.keys()
if len(judges) != 1: return -1
judge = judges.pop()
for p, trusted in person.items():
if judge not in trusted: return -1
return judge
- code
class Solution {
public int findJudge(int n, int[][] trust) {
if (trust.length < n - 1) return -1;
int[] out_in = new int[n+1];
for (int[] edge: trust){
out_in[edge[0]] --;
out_in[edge[1]] ++;
}
for (int i = 1; i < n + 1; i++){
if (out_in[i] == n - 1) return i;
}
return -1;
}
}