997. Find the Town Judge
Easy
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.
Solution
class Solution:
def findJudge(self, n: int, trust: List[List[int]]) -> int:
if n == 1:
return 1
people = set(range(1, n + 1))
trusts = set()
d = {}
for x, y in trust:
trusts.add(x)
if y in d:
d[y].add(x)
else:
d[y] = set([x])
for p in people - trusts:
if p in d and len(d[p]) == n - 1:
return p
return -1